[Li Kou - dynamic planning] sort out topic 1: basic topics: 509, 70, 746, 62, 63, 343, 96 (with links, topic descriptions, problem solving methods and codes)

If it helps you
Praise the blogger
Praise is the biggest encouragement to bloggers
Love launches ~

Code Capriccio knowledge planet

Basic knowledge of

• Dynamic programming is derived from the previous state
• The greedy algorithm chooses the best locally and directly

The problem solving steps

1. determine dp Array （dp table） And the meaning of subscripts
2. Determine the recurrence formula
3. dp How to initialize an array
4. Determine the traversal order
5. Give an example to deduce dp Array

The problem solving steps - concise

1. determine dp Array subscript meaning
2. The recursive formula
3. initialization
4. traversal order
5. The derivation results

509. Fibonacci number

Power button

Dynamic programming

class Solution {
    
    public int fib(int n) {
    
        /*  Dynamic programming : 1.  determine dp Array （dp table） And the meaning of subscripts  -  The first i Fibonacci Numbers   Value  2.  Determine the recurrence formula  - F(n) = F(n - 1) + F(n - 2) 3. dp How to initialize an array  - F(0) = 0,F(1) = 1 4.  Determine the traversal order  -  From before to after  5.  Give an example to deduce dp Array  - 0 1 1 2 3 5 8 13 21 34 55 */
        if(n < 2) return n;
        int a=0, b=1, c=0;
        for(int i=1; i<n; ++i){
    
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

70. climb stairs

Power button

Dynamic programming

class Solution {
    
    public int climbStairs(int n) {
    
        /*  Dynamic programming ： 1.  determine dp Array （dp table） And the meaning of subscripts  -  Climb the first n A stair , Yes dp[n] Methods  2.  Determine the recurrence formula  - dp[n] = dp[n-1] + dp[n-2] 3. dp How to initialize an array  - dp[1]=1 dp[2]=2 4.  Determine the traversal order  -  From front to back  5.  Give an example to deduce dp Array  - 1、2、3、5、8 */
        if(n<=2) return n;
        int a=1, b=2,c=0;
        for(int i=2; i<n; ++i){
    
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

746. Use the minimum cost to climb the stairs

Power button

Dynamic programming

class Solution {
    
    public int minCostClimbingStairs(int[] cost) {
    
        /* 1.  determine dp Array （dp table） And the meaning of subscripts  -  To the first i The minimum physical strength required for a step  2.  Determine the recurrence formula  - dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]; 3. dp How to initialize an array  - dp[0] = cost[0], dp[1] = cost[1] 4.  Determine the traversal order  -  From front to back  5.  Give an example to deduce dp Array  */
        if(cost == null || cost.length == 0) return 0;
        if(cost.length == 1) return cost[0];
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i=2; i<cost.length; ++i){
    
            dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i];
        }
        return Math.min(dp[cost.length-1], dp[cost.length -2]);
    }
}

62. Different paths

Power button

Dynamic programming

class Solution {
    
    public int uniquePaths(int m, int n) {
    
        /* 1.  determine dp Array subscript meaning —— dp[i][j]  Possible path types to each coordinate  2.  The recursive formula —— dp[i][j] = dp[i-1][j]+ dp[i][j-1] 3.  initialization —— dp[i][0]=1 dp[0][i]=1  Initialization can be done horizontally or vertically  4.  traversal order ——  Line by line  5.  The derivation results  */
        int[][] dp = new int[m][n];
        for(int i=0; i<m; ++i){
    
            dp[i][0] = 1;
        }
        for(int i=0; i<n; ++i){
    
            dp[0][i] = 1;
        }
        for(int i=1; i<m; ++i){
    
            for(int j=1; j<n; ++j){
    
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

63. Different paths II

Power button

Dynamic programming

class Solution {
    
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    
        /* 1.  determine dp Array subscript meaning ——  To dp[i][j] There are several paths  2.  The recursive formula  —— dp[i][j] = dp[i][j-1] + dp[i-1][j] 3.  initialization  —— dp[][]  Loop initialization , Encounter obstacles , Jump out of , All behind 0 4.  traversal order  ——  From before to after , One layer at a time  5.  The derivation results  */
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for(int i=0; i<m && obstacleGrid[i][0]==0; ++i){
    
            dp[i][0] = 1;
        }
        for(int i=0; i<n && obstacleGrid[0][i]==0; ++i){
    
            dp[0][i] = 1;
        }
        for(int i=1; i<m; ++i){
    
            for(int j=1; j<n; ++j){
    
                if(obstacleGrid[i][j]==1){
    
                    continue;
                }
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        return dp[m-1][n-1];

    }
}

343. integer partition

Power button

Dynamic programming

class Solution {
    
    public int integerBreak(int n) {
    
        /* 1.  determine dp Array subscript meaning ——  Numbers i The maximum product obtained dp[i] 2.  The recursive formula  —— dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j}); 3.  initialization  —— dp[2]=1 , dp[3]=2 4.  traversal order  ——  From before to after   outside i from 3 Start . From 1 5.  The derivation results  */
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i=3; i<=n; ++i){
    
            for(int j=1; j<=i-j; ++j){
    
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
            }
        }
        return dp[n];
    }
}

96. Different binary search trees

Power button

Carter LAN number

class Solution {
    
    public int numTrees(int n) {
    
        //  Carter LAN number 
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<=n; ++i){
    
            for(int j=1; j<=i; ++j){
    
                dp[i] += dp[j-1] * dp[i -j];
            }
        }
        return dp[n];
    }
}