代码随想录算法训练营第38天|动态规划理论基础 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯

动态规划理论基础

动态规划，简称DP，主要用来

DP五步：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

DP处理的问题：

?

图片来源：代码随想录?

509.?斐波那契数

五步曲：

1. 第i个数的值为dp[i]
2. 递推公式直接题里明说
3. 初始化也给了
4. 遍历顺序从前往后
5. debug用

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

70.?爬楼梯

五步曲：

1. dp[i]表示第i个台阶有dp[i]种方法
2. 递推公式：dp[i - 1] + dp[i - 2] = dp[i]
3. 初始化：dp[1] = 1, dp[2] = 2
4. 遍历顺序：从前向后
5. 举例子

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) 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.?使用最小花费爬楼梯

五步曲：

1. ?到达第i台阶所花费的最少体力为dp[i]
2. dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
3. 初始化：dp[0] = 0, dp[1] = 0
4. 从前到后
5. 举例子

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp0 = 0;
        int dp1 = 0;
        for (int i = 2; i <= cost.size(); i++) {
            int dpi = min(dp0 + cost[i - 2], dp1 + cost[i - 1]);
            dp0 = dp1;
            dp1 = dpi;
        }
        return dp1;
    }
};