动态规划

作者: mensa
Icon发表于2026-05-12
Icon更新于2026-05-15
Iconleetcode热题100
Icon

这是一篇关于 leetcode 动态规划的笔记。

思路

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

  1. 确定dp数组（dp table）以及下标的含义

  2. 确定递推公式

  3. dp数组如何初始化

  4. 确定遍历顺序

  5. 举例推导dp数组

70. 爬楼梯

思路分析：倒推法

想象你站在第 nn 阶台阶上，你是怎么上来的？

  • 你可能从第 n−1n-1 阶跳了 1 步上来的。

  • 你也可能从第 n−2n-2 阶跳了 2 步上来的。

所以，到达第 nn 阶的方法总数，就等于到达 n−1n-1 阶的方法数加上到达 n−2n-2 阶的方法数。

这就是著名的状态转移方程：

f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)

解法一：动态规划（空间优化版）

虽然我们可以开一个数组来存所有的值，但由于 f(n)f(n) 只依赖于前两个数，我们只需要两个变量来滚动记录即可。这种做法的时间复杂度是 O(n)O(n)，空间复杂度是 O(1)O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def climbStairs(self, n: int) -> int:
        # 处理特殊边界情况
        if n <= 2:
            return n
        
        # 1. 创建 dp 数组，长度为 n+1 (为了让下标对应楼层)
        dp = [0] * (n + 1)
        
        # 2. 设置初始值
        dp[1] = 1
        dp[2] = 2
        
        # 3. 按顺序填充数组
        for i in range(3, n + 1):
            dp[i] = dp[i-1] + dp[i-2]
            
        # 4. 返回最终状态
        return dp[n]

118. 杨辉三角

动态规划思路

我们可以把杨辉三角看作一个二维数组（或者是嵌套列表）。

  1. 状态定义：设 f(i,j)f(i, j) 为第 ii 行第 jj 列的数字。

  2. 转移方程：

  3. 对于非首尾元素：

  4. f(i,j)=f(i−1,j−1)+f(i−1,j)f(i, j) = f(i-1, j-1) + f(i-1, j)

  5. 边界条件：

  6. 每一行的第一个元素和最后一个元素都是 1：

  7. f(i,0)=1,f(i,i)=1f(i, 0) = 1, \quad f(i, i) = 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        # 初始化结果列表
        triangle = []

        for i in range(numRows):
            # 每一行的长度为 i + 1，先用 1 填充（这样首尾就自动处理好了）
            row = [1] * (i + 1)
            
            # 从第 3 行（索引为 2）开始，处理中间部分的元素
            # 中间元素的索引范围是 [1, i-1]
            for j in range(1, i):
                # 当前元素 = 上一行的左上方元素 + 上一行的正上方元素
                row[j] = triangle[i-1][j-1] + triangle[i-1][j]
            
            triangle.append(row)
            
        return triangle

198. 打家劫舍

动态规划思路：状态转移

我们可以通过构建一个递推关系来解决：

  1. 定义状态：

  2. 设 dp[i]dp[i] 为偷到第 ii 间房屋时，能够获得的最高金额。

  3. 状态转移方程：

  4. 当我们走到第 ii 间房（金额为 nums[i]nums[i]）时，我们有两种选择：

    • 选择偷：那么我们就不能偷第 i−1i-1 间房，所以总金额 = 第 i−2i-2 间房的最优解 + 当前房间金额：dp[i−2]+nums[i]dp[i-2] + nums[i]。

    • 选择不偷：那么我们可以维持偷到第 i−1i-1 间房时的最优解：dp[i−1]dp[i-1]。

  5. 为了钱更多，我们取两者的最大值：

  6. dp[i]=max⁡(dp[i−1],dp[i−2]+nums[i])dp[i] = \max(dp[i-1], dp[i-2] + nums[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def rob(self, nums: List[int]) -> int:
        # 边界处理
        if not nums: return 0
        if len(nums) == 1: return nums[0]
        
        # 1. 确定 dp 数组及其下标含义
        dp = [0] * len(nums)
        
        # 3. dp 数组初始化
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        
        # 4. 确定遍历顺序
        for i in range(2, len(nums)):
            # 2. 确定递推公式
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
            
        return dp[-1]

279. 完全平方数

我们要寻找的是：和为 nn 的完全平方数的最少数量。

① 确定 dp 数组（dp table）以及下标的含义

  • dp[i]：和为 ii 的完全平方数的最少数量。

  • 我们的目标是计算出 dp[n]。

② 确定递推公式

对于每一个数 ii，我们可以尝试减去一个完全平方数 j2j^2（其中 j2≤ij^2 \le i）。

如果我们减去了 j2j^2，那么剩下的数就是 i−j2i - j^2。此时所需的平方数数量就是 dp[i - j*j] + 1。

为了找到最少数量，我们需要遍历所有可能的 jj：

dp[i]=min⁡(dp[i],dp[i−j2]+1)dp[i] = \min(dp[i], dp[i - j^2] + 1)

其中 j∈[1,⌊i⌋]j \in [1, \lfloor \sqrt{i} \rfloor]。

③ dp 数组如何初始化

  • dp[0] = 0：和为 0 的最少平方数数量显然是 0。

  • 非零下标初始化：因为我们要取的是最小值（min），所以非零位置应初始化为一个极大值。在 Python 中可以用 float('inf') 或者 n+1n+1（因为最坏情况全是 1，数量不会超过 nn）。

④ 确定遍历顺序

  • 由于 dp[i] 取决于比它小的状态 dp[i - j^2]，所以必须从前向后遍历。

  • 外层循环：遍历数字 ii（从 1 到 nn）。

  • 内层循环：遍历可能的完全平方数 j2j^2。

⑤ 举例推导 dp 数组

以 n=4n=4 为例：

  1. dp[0] = 0

  2. i = 1: 只能减去 121^2。dp[1]=dp[1−1]+1=1dp[1] = dp[1-1] + 1 = 1

  3. i = 2: 只能减去 121^2。dp[2]=dp[2−1]+1=2dp[2] = dp[2-1] + 1 = 2

  4. i = 3: 只能减去 121^2。dp[3]=dp[3−1]+1=3dp[3] = dp[3-1] + 1 = 3

  5. i = 4:

    • 减去 121^2：dp[4−1]+1=4dp[4-1] + 1 = 4

    • 减去 222^2：dp[4−4]+1=1dp[4-4] + 1 = 1

    • 取最小值：dp[4] = 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import math

class Solution:
    def numSquares(self, n: int) -> int:
        # 1. 确定 dp 数组及其含义
        # dp[i] 表示和为 i 的完全平方数的最少数量
        dp = [float('inf')] * (n + 1)
        
        # 3. 初始化
        dp[0] = 0
        
        # 4. 确定遍历顺序
        for i in range(1, n + 1):
            # 2. 确定递推公式
            # 尝试所有小于等于 i 的完全平方数 j*j
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
                
        return dp[n]

322. 零钱兑换

image-20260512220725998

假设输入为 coins = [1, 2, 5], amount = 11。

① 确定 dp 数组（dp table）以及下标的含义

  • dp[j]：凑足总额为 j 所需的最少硬币个数。
  • 最终我们需要的结果是 dp[amount]。

② 确定递推公式

对于凑成金额 j，如果我们使用了硬币 coin，那么剩下的金额就是 j - coin。

此时凑成金额 j 的硬币数就是：dp[j - coin] + 1（加 1 是因为用了这一枚 coin）。

我们要找的是最少数，所以要在所有可能的硬币选项中取最小值：

dp[j]=min⁡(dp[j],dp[j−coin]+1)dp[j] = \min(dp[j], dp[j - coin] + 1)

注意：只有当 j - coin >= 0 且 dp[j - coin] 是可达到的（不是初始的极大值）时，才进行转移。

③ dp 数组如何初始化

  • dp[0] = 0：凑足金额为 0 需要 0 枚硬币。
  • 非零下标初始化：因为我们要取的是最小值（min），所以非零位置应初始化为一个极大值。
    • 在 Python 中可以用 float('inf')。
    • 或者初始化为 amount + 1，因为即使全部用 1 元硬币，数量也不会超过 amount。

④ 确定遍历顺序

由于硬币数量是无限的，这是一个完全背包问题。

  • 外层循环：遍历金额 j 从 1 到 amount。

  • 内层循环：遍历硬币列表 coins。

    （注：求最少硬币数时，先遍历硬币还是先遍历金额其实都可以，但通常先遍历金额更符合“从小问题推到大问题”的直觉。）

⑤ 举例推导 dp 数组

以 coins = [1, 2, 5], amount = 5 为例：

  1. dp[0] = 0
  2. j = 1: dp[1] = dp[1-1] + 1 = 1
  3. j = 2:
    • 选 1: dp[2-1] + 1 = 2
    • 选 2: dp[2-2] + 1 = 1
    • 取最小：dp[2] = 1
  4. j = 3:
    • 选 1: dp[3-1] + 1 = 1+1 = 2
    • 选 2: dp[3-2] + 1 = 1+1 = 2
    • 取最小：dp[3] = 2
  5. … 依此类推直到 j = 5，最后 dp[5] = 1（直接用一枚 5 元）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 1. 确定 dp 数组及其下标含义
        # 初始化为 amount + 1 效果等同于无穷大
        dp = [amount + 1] * (amount + 1)
        
        # 3. 初始化边界条件
        dp[0] = 0
        
        # 4. 确定遍历顺序
        for j in range(1, amount + 1):  # 遍历金额（背包）
            for coin in coins:          # 遍历硬币（物品）
                # 2. 确定递推公式
                if j >= coin:
                    dp[j] = min(dp[j], dp[j - coin] + 1)
        
        # 5. 返回结果
        # 如果 dp[amount] 依然是初始值，说明凑不出来，返回 -1
        return dp[amount] if dp[amount] <= amount else -1

139. 单词拆分

image-20260512221530433

假设输入为 s = "leetcode", wordDict = ["leet", "code"]。

① 确定 dp 数组（dp table）以及下标的含义

  • dp[i]：字符串 ss 的前 ii 个字符（即子串 s[0:i]）是否可以被拆分为字典中的单词。
  • dp[i] 为布尔类型（True 或 False）。
  • 最终目标：计算出 dp[len(s)]。

② 确定递推公式

如果 dp[j] 是 True（代表前 jj 个字符已经可以拆分成功），那么我们只需要判断剩下的子串 s[j:i] 是否在字典中。

如果 s[j:i] 也在字典中，那么 dp[i] 就可以被确认为 True。

递推公式：

dp[i] = True (如果存在一个 j<ij < i，使得 dp[j] == True 且 s[j:i] 在 wordDict 中)

③ dp 数组如何初始化

  • dp[0] = True：空字符串默认可以拆分（这是递推的基石，如果没有它，后面所有的 dp[i] 都会永远是 False）。
  • 其他下标初始化为 False。

④ 确定遍历顺序

由于 dp[i] 依赖于它之前的状态 dp[j]，所以必须从前往后遍历。

  • 外层循环：遍历子串的结束位置 ii（从 1 到 len(s)）。
  • 内层循环：遍历分割点 jj（从 0 到 ii）。

⑤ 举例推导 dp 数组

以 s = "leetcode", wordDict = ["leet", "code"] 为例：

  1. dp[0] = True

  2. i=1i = 1 到 33：找不到任何 jj 满足条件。("l", "le", "lee" 都不在字典里)

  3. i=4i = 4：当 j=0j = 0 时，dp[0] 是 True 且 s[0:4] ("leet") 在字典中，所以 dp[4] = True。

  4. i=5i = 5 到 77：继续向后尝试。

  5. i=8i = 8：当 j=4j = 4 时，dp[4] 是 True 且 s[4:8] ("code") 在字典中，所以 dp[8] = True。

    最终返回 True。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 1. 确定 dp 数组及其下标含义
        # dp[i] 表示 s 的前 i 个字符是否可以拆分
        dp = [False] * (len(s) + 1)
        
        # 3. 初始化
        dp[0] = True
        
        # 为了提高查询速度，转为集合
        word_set = set(wordDict)
        
        # 4. 确定遍历顺序
        for i in range(1, len(s) + 1):  # 结束位置
            for j in range(i):          # 分割位置
                # 2. 确定递推公式
                # 如果前 j 个字符能拆分，且剩余部分在字典中
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break # 只要找到一种拆分方式，dp[i] 就是 True，可以跳出内层循环
                    
        return dp[len(s)]

300. 最长递增子序列

image-20260512222220445

假设输入数组为 nums = [10, 9, 2, 5, 3, 7, 101, 18]。

① 确定 dp 数组（dp table）以及下标的含义

  • dp[i]：以 nums[i] 结尾的最长严格递增子序列的长度。
  • 注意：一定要包含 nums[i] 这个元素，这样在后续状态转移时，我们才有明确的参照点。
  • 最终结果：不是 dp[n-1]，而是整个 dp 数组中的最大值 max(dp)。

② 确定递推公式

对于 dp[i]，我们需要检查在它之前的所有位置 j（即 0≤j<i0 \le j < i）：

  • 如果 nums[i] > nums[j]：说明 nums[i] 可以接在以 nums[j] 结尾的子序列后面，构成一个新的递增子序列。此时长度为 dp[j] + 1。

  • 我们需要在所有满足条件的 j 中取最大值。

  • 递推公式：

    dp[i]=max⁡(dp[i],dp[j]+1)其中 0≤j<i 且 nums[i]>nums[j]dp[i] = \max(dp[i], dp[j] + 1) \quad \text{其中 } 0 \le j < i \text{ 且 } nums[i] > nums[j]

③ dp 数组如何初始化

  • 每个元素自身都可以看作一个长度为 1 的递增子序列。
  • 因此，dp 数组的所有位置都应初始化为 1。

④ 确定遍历顺序

  • dp[i] 取决于它之前的状态 dp[j]，所以必须从前向后遍历。
  • 外层循环 ii：从 00 遍历到 n−1n-1。
  • 内层循环 jj：从 00 遍历到 i−1i-1。

④ 举例推导 dp 数组

以 nums = [10, 9, 2, 5, 3] 为例：

  1. i = 0: nums[0]=10, dp[0]=1

  2. i = 1: nums[1]=9。j=0,9<10j=0, 9 < 10，不更新。dp[1]=1

  3. i = 2: nums[2]=2。j=0,1,2<9,10j=0, 1, 2 < 9, 10，不更新。dp[2]=1

  4. i = 3: nums[3]=5。

    • j=0,1j=0, 1 时不满足。
    • j=2j=2 时，5>25 > 2，dp[3] = max(1, dp[2] + 1) = 2。

  5. i = 4: nums[4]=3。

    • j=2j=2 时，3>23 > 2，dp[4] = max(1, dp[2] + 1) = 2。

      最终 max(dp) 为 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        # 1. 确定 dp 数组及其下标含义
        # 3. 初始化为 1
        dp = [1] * len(nums)
        
        # 4. 确定遍历顺序
        for i in range(len(nums)):
            for j in range(i):
                # 2. 确定递推公式
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        # 最后返回 dp 数组中的最大值
        return max(dp)

152. 乘积最大子数组

image-20260512223503679

既然你强调要严格执行“动态规划五步曲”，那我们就把这套标准模版套用到 152. 乘积最大子数组 上。这道题是五步曲训练的绝佳素材，因为它涉及到了状态的“双生”关系。

152. 乘积最大子数组 —— 动态规划五步曲

假设输入数组为 nums = [2, 3, -2, 4]。

① 确定 dp 数组（dp table）以及下标的含义

由于乘法中存在“负负得正”的情况，仅仅记录最大值是不够的，我们必须同时记录最小值（因为当前的最小值一旦乘以一个负数，可能瞬间变成最大值）。

  • dp_max[i]：表示以 nums[i] 结尾的连续子数组的最大乘积。
  • dp_min[i]：表示以 nums[i] 结尾的连续子数组的最小乘积。
  • 注意：子数组必须连续且包含 nums[i]。

② 确定递推公式

对于第 ii 个数 nums[i]nums[i]，dp_max[i] 只能从以下三个值中产生：

  1. 不接前面的：直接就是 nums[i]nums[i]。
  2. 接前面的大值：dp_max[i−1]×nums[i]dp\_max[i-1] \times nums[i]（当 nums[i]>0nums[i] > 0 时有效）。
  3. 接前面的小值：dp_min[i−1]×nums[i]dp\_min[i-1] \times nums[i]（当 nums[i]<0nums[i] < 0 且之前有大负数时有效）。

因此递推公式为：

dp_max[i]=max⁡(nums[i],dp_max[i−1]×nums[i],dp_min[i−1]×nums[i])dp\_max[i] = \max(nums[i], dp\_max[i-1] \times nums[i], dp\_min[i-1] \times nums[i])

dp_min[i]=min⁡(nums[i],dp_max[i−1]×nums[i],dp_min[i−1]×nums[i])dp\_min[i] = \min(nums[i], dp\_max[i-1] \times nums[i], dp\_min[i-1] \times nums[i])

③ dp 数组如何初始化

  • 第一个数无法向前结合，所以它既是最大也是最小：
    • dp_max[0]=nums[0]dp\_max[0] = nums[0]
    • dp_min[0]=nums[0]dp\_min[0] = nums[0]
  • 其他位置可以根据这个起点开始推导。

④ 确定遍历顺序

  • 因为 dp[i]dp[i] 的值严谨依赖于 dp[i−1]dp[i-1] 的值，所以必须从前往后遍历。
  • 从 i=1i = 1 遍历到 n−1n-1。

⑤ 举例推导 dp 数组

以 nums = [2, 3, -2, 4] 为例，手动推导过程如下：

i nums[i] dp_max[i] dp_min[i] 说明
0 2 2 2 初始化
1 3 max⁡(3,2×3,2×3)=6\max(3, 2 \times 3, 2 \times 3) = \mathbf{6} min⁡(3,2×3,2×3)=3\min(3, 2 \times 3, 2 \times 3) = \mathbf{3} 延续增长
2 -2 max⁡(−2,6×−2,3×−2)=−2\max(-2, 6 \times -2, 3 \times -2) = \mathbf{-2} min⁡(−2,6×−2,3×−2)=−12\min(-2, 6 \times -2, 3 \times -2) = \mathbf{-12} 遭遇负数，极值反转
3 4 max⁡(4,−2×4,−12×4)=4\max(4, -2 \times 4, -12 \times 4) = \mathbf{4} min⁡(4,−8,−48)=−48\min(4, -8, -48) = \mathbf{-48} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        
        # 1. 确定 dp 数组及其下标含义
        dp_max = [0] * n
        dp_min = [0] * n
        
        # 3. 初始化
        dp_max[0] = nums[0]
        dp_min[0] = nums[0]
        
        # 4. 确定遍历顺序
        for i in range(1, n):
            # 2. 确定递推公式
            # 注意：在比较时需要考虑 nums[i] 乘以之前最大和最小的两种情况
            num_1 = dp_max[i-1] * nums[i]
            num_2 = dp_min[i-1] * nums[i]
            
            dp_max[i] = max(nums[i], num_1, num_2)
            dp_min[i] = min(nums[i], num_1, num_2)
            
        # 最终答案是 dp_max 中的最大值
        return max(dp_max)

416. 分割等和子集

image-20260512223916665

1

Icon
致谢名单
本作品由 mensa 于 2026-05-12 10:00:00 发布
作品地址：动态规划
除特别声明外，本站作品均采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ColdWater
Logo
上一篇Transformer 整体结构下一篇1.使用 Cloudflare + GitHub + Hexo 搭建高效免费的个人博客