力扣509 斐波那契数

https://leetcode.cn/problems/fibonacci-number/

/*
递推就是初级dp思路
*/
class Solution {
public:
    int fib(int n) {
        if (n == 0)
            return 0;
        else if (n < 2)
            return 1;

        vector<int> dp(n + 1, 0);
        dp[1] = 1;

        for (int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];

        return dp[n];
    }
};

力扣70 爬楼梯

https://leetcode.cn/problems/climbing-stairs/

/*
i时刻有两种选择：从i-1走过来或是从i-2走过来，所以要累计两种方法的和
该题不存在dp[0]的情况
*/
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1)
            return n;

        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];
    }
};

力扣746 使用最小花费爬楼梯

https://leetcode.cn/problems/min-cost-climbing-stairs/

/*
初始化dp数组的原则取决于递推关系，比如斐波那契数，只需要初始化f0和f1，后面的都可以通过递推的方法求出来，dp问题亦是如此
特别要注意的是i=0时的状态，如果是实际问题可能不需要，如果是数组之类的可能就需要初始化
*/
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);  // 针对cost

        dp[0] = cost[0];  // 后续都可以通过递推方法求出来
        dp[1] = cost[1];  // 而且条件是从0从1开始，所以肯定要初始化

        for (int i = 2; i < n; i++)
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

        // 注意这里，题目说的是爬到楼顶，所以要看最后一位(前进一步)和最后第二位(前进两步)，代价在上面dp更新里
        int res = min(dp[n - 1], dp[n - 2]);
        return res;
    }
};

力扣62 不同路径

https://leetcode.cn/problems/unique-paths/

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 不同路径2

https://leetcode.cn/problems/unique-paths-ii/

/*
在前一题的基础上加了障碍物的判断和初始化，比如00100，前面两个00可以到达所以初始化为1，后面俩不行
*/
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));

        for (int i = 0; i < m && grid[i][0] == 0; i++)
            dp[i][0] = 1;
        for (int j = 0; j < n && grid[0][j] == 0; j++)  // 对边缘没有障碍物的地方初始化
            dp[0][j] = 1;

        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
            {
                if (grid[i][j] == 1)  // 如果是障碍物就跳过
                    continue;

                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        return dp[m - 1][n - 1];
    }
};