阅读量:0
一、动态规划理论基础
文章讲解：代码随想录 (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)]