代码随想录第28天：动态规划1

一、什么是动态规划

Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

动态规划中每一个状态一定是由上一个状态推导出来的，而贪心没有状态推导，而是从局部直接选最优的。

解决动态规划问题的五部思考流程，代码随想录Carl总结为“动规五部曲”：

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

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，如果代码没通过就打印dp数组，找出哪里和自己预先推导的不一样。如果和自己预先模拟推导是一样的，那就是递归公式、初始化或者遍历顺序有问题，如果和自己预先模拟推导的不一样，那么大概率是代码实现细节有问题。

二、斐波那契数（Leetcode 509）

class Solution:def fib(self, n: int) -> int:# 边界情况处理：如果n为0，直接返回0if n == 0:return 0# 创建一个大小为n+1的列表，用来存储从0到n的Fibonacci数dp = [0] * (n + 1)# dp数组初始化：dp[0] = 0 和 dp[1] = 1dp[0], dp[1] = 0, 1 # 从第2个元素开始，计算Fibonacci数列的每个数for i in range(2, n + 1):# 递推公式：dp[i]是dp[i-1]和dp[i-2]的和，即Fibonacci数列的定义dp[i] = dp[i - 1] + dp[i - 2]# 返回第n个Fibonacci数return dp[n]

三、爬楼梯（Leetcode 70）

1.确定dp数组以及下标的含义：达到  i 阶有dp[i] 种方法

2.确定递推公式：

dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，下一步跳一个台阶就是dp[i]。

dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，下一步跳两个台阶就是dp[i]。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和

dp[i] = dp[i - 1] + dp[i - 2]

3.dp数组如何初始化：dp[0] = 1（没有实际意义）dp[1] = 1, dp[2] = 2

4.确定遍历顺序：从前向后遍历

5.举例推导dp数组（debug用）

class Solution:def climbStairs(self, n: int) -> int:# 如果楼梯的级数小于等于1，直接返回n# 即：如果楼梯有0级或1级，只有一种方式（直接站着或爬一步）if n <= 1:return n# 初始化一个大小为n+1的dp数组，用来存储从0到n级台阶的方法数dp = [0] * (n + 1)# 基础情况：# dp[1]表示爬到第1级台阶有1种方法（一步到达）# dp[2]表示爬到第2级台阶有2种方法（一步一步爬，或者一次爬两步）dp[1] = 1dp[2] = 2# 从第3级台阶开始，计算每个台阶的爬法总数for i in range(3, n + 1):# dp[i]是通过从第i-1级台阶爬1步或从第i-2级台阶爬2步到达的dp[i] = dp[i - 1] + dp[i - 2]# 返回爬到第n级台阶的方法总数return dp[n]

四、使用最小花费爬楼梯（Leetcode 746）

1.确定dp数组以及下标的含义：到达第i台阶所花费的最少体力为dp[i]。

2.确定递推公式：

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么

dp[i] = min( dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2] )

3.dp数组如何初始化：根据dp数组的定义，到达第0台阶所花费的最小体力为dp[0], 初始化 dp[0] = 0，dp[1] = 0;

4.确定遍历顺序：从前向后遍历

5.举例推导dp数组（debug用）:

cost = [ 1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

dp = [0, 0, 1, 2, 2, 3, 3, 4, 4, 5, 6]

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:# 创建一个大小为len(cost)+1的dp数组，dp[i]表示到达第i个台阶的最小费用dp = [0] * (len(cost) + 1)# 初始化dp[0]和dp[1]，爬到第0个和第1个台阶不需要额外的费用dp[0], dp[1] = 0, 0# 从第2个台阶开始，计算每个台阶到达的最小费用for i in range(2, len(cost) + 1):# dp[i]是从第i-1个台阶或第i-2个台阶跳跃到当前台阶所花的最小费用dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])# 返回到达最后一个或倒数第二个台阶的最小费用return dp[len(cost)]