代码随想录算法训练营第三十八天｜理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

理论基础 - 🔗

动态规划，英文：Dynamic Programming，简称DP。动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

动态规划五部曲：

• 确定dp数组（dp table）以及下标的含义
• 确定递推公式（个人做题发现，最好不要从头理解是如何往后递推的，会绕不出来，直接找中间任意一个节点，去思考如何得到这个节点的值）
• dp数组如何初始化
• 确定遍历顺序
• 举例推导dp数组

509. 斐波那契数 - 🔗

讲解 - 🔗
💡动态规划五部曲：

1. 确定dp数组（dp table）以及下标的含义：dp[i]表示下标为i的斐波那契数F(i)的值。
2. 确定递推公式：读题可得dp[i] = dp[i - 1] + dp[i - 2]
3. dp数组如何初始化：读题可得 - dp[0] = 0, dp[1] = 1
4. 确定遍历顺序 从前往后
5. 举例推导dp数组

class Solution:
    def fib(self, n: int) -> int:
        # 确定dp数组（dp table）以及下标的含义
        dp = [0] * (n + 1)
        # 确定递推公式 dp[i] = dp[i - 1] + dp[i - 2]
        
        for i in range(0, n + 1): # 确定遍历顺序
            # 初始化dp数组
            if i == 0:
                dp[i] = 0
            elif i == 1:
                dp[i] = 1
            else:
                dp[i] = dp[i - 1] + dp[i - 2]
        return dp[-1]

70. 爬楼梯 - 🔗

讲解 - 🔗
💡动态规划五部曲：

1. 确定dp数组（dp table）以及下标的含义：dp[i]代表爬到第i阶台阶的方法数
2. 确定递推公式：假设当前台阶为第i个台阶，可以发现要想走到第i个台阶，有两种方式，一是从第i-2个台阶走两步，二是从第i-1个台阶走一步，再根据dp[i]的定义，因此dp[i] = dp[i - 1] + dp[i - 2]
3. dp数组如何初始化：dp[0] = 1, dp[1] = 2
4. 确定遍历顺序 从前往后
5. 举例推导dp数组

class Solution:
    def climbStairs(self, n: int) -> int:
        # 确定dp数组（dp table）以及下标的含义
        dp = [0] * n
        # 确定递推公式 dp[i] = dp[i - 1] + dp[i - 2]
        # dp数组如何初始化 dp[0] = 1 dp[1] = 2
        # 确定遍历顺序 前往后
        # 举例推导dp数组
        for i in range(n): # 确定遍历顺序
            # 初始化dp数组
            if i == 0:
                dp[i] = 1
            elif i == 1:
                dp[i] = 2
            else:
                dp[i] = dp[i - 1] + dp[i - 2]
        return dp[-1]

746. 使用最小花费爬楼梯 - 🔗

讲解 - 🔗
💡动态规划五部曲：

1. 确定dp数组（dp table）以及下标的含义：dp[i]代表爬到第i阶台阶的最小花费
2. 确定递推公式：假设当前台阶为第i个台阶，可以发现要想求走到第i个台阶的花费，有两种方式，一是从第i-2个台阶走两步，花费为dp[i - 2] + cost[i - 2]；二是从第i-1个台阶走一步，花费为dp[i - 1] + cost[i - 1]。再根据dp[i]的定义，因此dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
3. dp数组如何初始化：读题可得 - dp[0] = dp[1] = 0，因为可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯
4. 确定遍历顺序 从前往后
5. 举例推导dp数组

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 确定dp数组（dp table）以及下标的含义 dp[i]表示到达第i层阶梯的最低花费
        # 确定递推公式 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        # dp数组如何初始化 dp[0] = dp[1] = 0，因为可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
        # 确定遍历顺序 从前往后
        # 举例推导dp数组
        dp = [0] * (len(cost) + 1)
        for i in range(2, len(dp)):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        return dp[-1]