Dynamic programming for solving problems (1)

Dynamic programming

summary ：

1.dp Definition and subscript of array .

2. The recursive formula .

3.dp How to initialize an array , Initialization also needs attention .

4. traversal order , More exquisite ,01 Go through the backpack first , After traversing the item .

4.1 The traversal order of permutation and combination is different .

4.1.1  array ： The backpack is outside   Items included .（322）

4.1.2  Combine ： The object is outside , Backpack inside .（518）

5.（ Problems arise ） Print dp Array .（ Print dp Array , Check for problems , test 1 2 3 4 step ）

Before you ask such a question , In fact, you can think about these three questions first ：

• Have I deduced the state transition formula for this topic ？
• I print dp Array logs ？
• It's printed dp Is the array the same as I thought

509. Fibonacci number

summary :i <= n

class Solution {
    
public:
    int fib(int N) {
    
        if (N <= 1) return N;
        vector<int> dp(N + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
    
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[N];
    }
};

• Time complexity ：O(n)
• Spatial complexity ：O(n)

Of course you can find , We only need to maintain two values , There is no need to record the whole sequence .

The code is as follows ：

class Solution {
    
public:
    int fib(int N) {
    
        if (N <= 1) return N;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
    
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

• Time complexity ：O(n)
• Spatial complexity ：O(1)

70. climb stairs

summary ： If you can launch dp[i] Well ？

from dp[i] The definition of ,dp[i] It can be pushed out in two directions .

First of all dp[i - 1], On i-1 Floor stairs , Yes dp[i - 1] Methods , So one more step is dp[i] Why? .

And that is dp[i - 2], On i-2 Floor stairs , Yes dp[i - 2] Methods , So, if you jump two steps further, it's just dp[i] Why? .

that dp[i] Namely dp[i - 1] And dp[i - 2] The sum of the ！

therefore dp[i] = dp[i - 1] + dp[i - 2] .

In derivation dp[i] When , Always think about dp[i] The definition of , Otherwise, it's easy to deviate

class Solution {
    
public:
    int climbStairs(int n) {
    
        if (n <= 1) return n;
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
    
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};

746. Use the minimum cost to climb the stairs

summary ：dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

dp[i] Representing the next step Physical strength , But the return is dp[i-1] or dp[i-2]

class Solution {
    
public:
    int minCostClimbingStairs(vector<int>& cost) {
    
        vector<int> dp(cost.size());
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.size(); i++) {
    
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        //  Note that the last step can be understood as no cost , So take the first step from the bottom , The minimum value of the second step 
        return min(dp[cost.size() - 1], dp[cost.size() - 2]);
    }
};

62. Different paths

Here's a look at the recursive formula dpi = dpi - 1 + dpi,dpi It's all derived from above and to the left , Then it's OK to traverse one layer from left to right .

summary ： Initialization is for 1 . Not for 0

for (int i = 0; i < m; i++) dpi = 1;

    class Solution {
    
    public:
        int uniquePaths(int m, int n) {
    
            vector<vector<int>> dp(m, vector<int>(n, 0));
            for (int i = 0; i < m; i++) dp[i][0] = 1;
            for (int j = 0; j < n; j++) dp[0][j] = 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

Initialization part , It's easy to ignore the obstacles. They should all be 0 The situation of .

summary ： Start black hole to 0, The other is 1. Just consider one , Start thinking for yourself , Multistep addition 3 It's wrong. , Share the current 1 Step And the former 2 Step .

class Solution {
    
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 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 - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

• Time complexity ：O(n × m),n、m Respectively obstacleGrid Length and width
• Spatial complexity ：O(n × m)