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

一、动态规划理论基础

文章讲解：代码随想录 (programmercarl.com)——动态规划理论基础

视频讲解：从此再也不怕动态规划了，动态规划解题方法论大曝光 ！| 理论基础 |力扣刷题总结| 动态规划入门_哔哩哔哩_bilibili

题目分类：
1. 动态规划基础；
2. 背包问题；
3. 打家劫舍；
4. 股票问题；
5. 子序列问题。

动态规划五部曲：
1. 确定 dp[ i ] 数组及下标含义；
2. 确定递推公式；
3. 确定dp数组如何初始化；
4. 确定遍历顺序（背包问题中很重要）；
5. 举例推导dp数组。

二、509. 斐波那契数

题目链接：509. 斐波那契数 - 力扣（LeetCode）
文章讲解：代码随想录 (programmercarl.com)——509. 斐波那契数
视频讲解：手把手带你入门动态规划 | LeetCode：509.斐波那契数_哔哩哔哩_bilibili

动态规划五部曲：
1. 确定 dp[ i ] 数组及下标含义：dp[i]表示第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:
        # 确定边界条件
        if n == 0 or n == 1:
            return n
 
        # 创建dp数组
        dp = [0] * (n + 1)
 
        # 初始化dp数组
        dp[0] = 0
        dp[1] = 1
 
        # 由前向后遍历
        for i in range(2, n + 1):
            # 确定递归公式
            dp[i] = dp[i - 1] + dp[i - 2]
 
        return dp[n]

三、70. 爬楼梯

题目链接：70. 爬楼梯 - 力扣（LeetCode）
文章讲解：代码随想录 (programmercarl.com)——70. 爬楼梯
视频讲解：带你学透动态规划-爬楼梯（对应力扣70.爬楼梯）| 动态规划经典入门题目_哔哩哔哩_bilibili

分析：
1阶——1种
2阶——2种
3阶——1阶走一步 + 2阶走一步 = 3种
4阶——2阶走一步 + 3阶走一步 = 5种
类似斐波那契数列，只是初始值设置不同。

动态规划五部曲：
1. 确定 dp[ i ] 数组及下标含义：达到第i阶有dp[i]种方法。
2. 确定递推公式：dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ]。
3. 确定dp数组如何初始化：dp[ 1 ] = 1, dp[ 2 ] = 2，dp[0]没有意义，题目要求为正整数。
4. 确定遍历顺序：从前向后遍历
5. 举例推导dp数组。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
            
        dp = [0] * (n + 1)
 
        dp[1] = 1
        dp[2] = 2
 
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
 
        return dp[n]

四、746. 使用最小花费爬楼梯

题目链接：746. 使用最小花费爬楼梯 - 力扣（LeetCode）
文章讲解：代码随想录 (programmercarl.com)——746. 使用最小花费爬楼梯
视频讲解：动态规划开更了！| LeetCode：746. 使用最小花费爬楼梯_哔哩哔哩_bilibili

动态规划五部曲：
1. 确定 dp[ i ] 数组及下标含义：到达 i 位置所需要的花费为 dp[ i ]。
2. 确定递推公式：dp[ i ]  = min( dp[ i - 1 ] + cost[ i - 1 ], dp[ i - 2 ] + cost[ i - 2 ] )。
3. 确定dp数组如何初始化：当前值可以由前两个值求得，且起始位置可以为 0 或 1 ，因此初始化 dp[0] = 0 和 dp[1] = 0。
4. 确定遍历顺序：从前向后遍历。
5. 举例推导dp数组。

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * (len(cost) + 1)
 
        # 初始化
        dp[0] = 0
        dp[1] = 0
 
        for i in range(2, len(cost) + 1):
            # 确定递推公式，为前一步和前两步中花费最少的
            # 每一步花费为 dp[i - 1] 加上当前的花费 cost[i - 1]
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
 
        return dp[len(cost)]