全国企业管理信息系统网站/企业微信scrm

代码随想录训练营 Day32打卡 动态规划 part01

一、 理论基础

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

例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

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

二、 力扣509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例 ：
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

版本一

如果 n 为 0，直接返回 0，这是 Fibonacci 序列的第一个值。
创建一个长度为 n + 1 的数组 dp，用于存储从第 0 到第 n 位的 Fibonacci 值。
dp[0] 和 dp[1] 分别初始化为 0 和 1，对应 Fibonacci 序列的前两个值。
从 i = 2 开始遍历，使用状态转移方程 dp[i] = dp[i - 1] + dp[i - 2] 计算每个位置的 Fibonacci 值。
最终返回 dp[n]，即为第 n 个 Fibonacci 数。

class Solution:def fib(self, n: int) -> int:# 排除 Corner Case，当 n 为 0 时，直接返回 0if n == 0:return 0# 创建 dp table 用于存储每个位置的 Fibonacci 值dp = [0] * (n + 1)# 初始化 dp 数组，Fibonacci 序列的前两个值dp[0] = 0dp[1] = 1# 遍历顺序: 由前向后。因为后面要用到前面的状态for i in range(2, n + 1):# 确定递归公式/状态转移公式dp[i] = dp[i - 1] + dp[i - 2]  # dp[i] 等于前两个状态的和# 返回答案，dp[n] 即为第 n 个 Fibonacci 数return dp[n]

版本二

如果 n 小于等于 1，直接返回 n，因为 Fibonacci(0) = 0 和 Fibonacci(1) = 1。
使用一个长度为 2 的列表 dp 来存储最近的两个 Fibonacci 值，初始为 [0, 1]。
从 i = 2 开始循环计算 Fibonacci 数，每次计算当前 Fibonacci 数并更新 dp 列表中的值。
返回 dp[1]，即为第 n 个 Fibonacci 数。

class Solution:def fib(self, n: int) -> int:# 如果 n 小于等于 1，直接返回 n（因为 Fibonacci(0) = 0, Fibonacci(1) = 1）if n <= 1:return n# 初始化 dp 数组，只保存最近的两个 Fibonacci 数dp = [0, 1]# 从 2 开始计算到 nfor i in range(2, n + 1):# 计算当前 Fibonacci 数，并更新 dp 数组total = dp[0] + dp[1]dp[0] = dp[1]  # 将 dp[1] 移到 dp[0] 位置dp[1] = total  # 新的 Fibonacci 数放在 dp[1] 位置# 返回 dp[1]，即为第 n 个 Fibonacci 数return dp[1]

版本三

如果 n 小于等于 1，直接返回 n，因为 Fibonacci(0) = 0 和 Fibonacci(1) = 1。
使用 prev1 和 prev2 分别存储前两个 Fibonacci 数，初始为 0 和 1。
从 i = 2 开始计算，每次更新 prev1 和 prev2，其中 curr 是当前计算出的 Fibonacci 数。
返回 prev2，即为第 n 个 Fibonacci 数。

class Solution:def fib(self, n: int) -> int:# 如果 n 小于等于 1，直接返回 nif n <= 1:return n# 使用两个变量存储前两个 Fibonacci 数prev1, prev2 = 0, 1# 从 2 开始计算到 nfor _ in range(2, n + 1):# 当前 Fibonacci 数是前两个数之和curr = prev1 + prev2# 更新 prev1 和 prev2prev1, prev2 = prev2, curr# 返回最后的 Fibonacci 数return prev2

力扣题目链接
题目文章讲解
题目视频讲解

三、 力扣70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。
dp[i]的定义：爬到第i层楼梯，有dp[i]种方法。

举例当n为5的时候，dp table（dp数组）应该是这样的

代码实现

如果 n 小于等于 1，直接返回 n。
通过使用两个变量 prev1 和 prev2 分别存储前两个台阶的方法数，进一步优化空间复杂度到 O(1)。
计算当前台阶的方法数 total，并更新 prev1 和 prev2，继续计算下一个台阶的方法数。
返回 prev2，即为到达第 n 级台阶的方法数。

# 空间复杂度为 O(1) 版本
class Solution:def climbStairs(self, n: int) -> int:# 处理边界情况，如果楼梯数为1或更少，直接返回n（0或1）if n <= 1:return n# 使用两个变量来存储前两个台阶的方法数，节省空间prev1 = 1  # 表示前两级台阶的方法数prev2 = 2  # 表示前一级台阶的方法数# 从第3级台阶开始计算for i in range(3, n + 1):# 当前台阶的方法数是前两个台阶的方法数之和total = prev1 + prev2prev1 = prev2  # 更新 prev1 为前一级台阶的方法数prev2 = total  # 更新 prev2 为当前台阶的方法数# 返回到达第n级台阶的方法数return prev2

力扣题目链接
题目文章讲解
题目视频讲解

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

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 ：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。

• 支付 15 ，向上爬两个台阶，到达楼梯顶部。
  总花费为 15 。

dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。

对于dp数组的定义，大家一定要清晰！

可以有两个途径得到dp[i]，一个是dp[i-1] 一个是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 - 1]跳还是从dp[i - 2]跳呢？

一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下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):# 在第i步，可以选择从前一步（i-1）花费体力到达当前步，或者从前两步（i-2）花费体力到达当前步# 选择其中花费体力较小的路径，加上当前步的花费，更新dp数组dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])return dp[len(cost)]  # 返回到达楼顶的最小花费

版本二

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:dp0 = 0  # 初始值，表示从起点开始不需要花费体力dp1 = 0  # 初始值，表示经过第一步不需要花费体力for i in range(2, len(cost) + 1):# 在第i步，可以选择从前一步（i-1）花费体力到达当前步，或者从前两步（i-2）花费体力到达当前步# 选择其中花费体力较小的路径，加上当前步的花费，得到当前步的最小花费dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2])dp0 = dp1  # 更新dp0为前一步的值，即上一次循环中的dp1dp1 = dpi  # 更新dp1为当前步的最小花费return dp1  # 返回到达楼顶的最小花费

力扣题目链接
题目文章讲解
题目视频讲解