dp--校训

题目一:斐波那契数

509. 斐波那契数 - 力扣（LeetCode）

代码1（递归）

class Solution {
public:
    int fib(int n) {
        if(n==0 || n==1) return n;
        return fib(n-1) + fib(n-2);
    }
};

代码2（dp打表）

class Solution {
public:
    int fib(int n) {
        if(n==0) return 0;
        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];
    }
};

题目二： 爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

代码

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

代码2

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

题目三：最小路径和

64. 最小路径和 - 力扣（LeetCode）

代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<int>> dp(m,vector<int>(n));
        dp[0][0] = grid[0][0];
        for(int j = 1; j < n; j ++) dp[0][j] = dp[0][j-1]+grid[0][j];
        for(int i = 1; i < m; i ++) dp[i][0] = dp[i-1][0]+grid[i][0];
        for(int i = 1; i < m; i ++) {
            //dp[i][0] = dp[i-1][0] + grid[i][0];
            for(int j = 1; j < n; j ++) {
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};