LeetCode（七）—— 动态规划入门

动态规划在算法学习里有种被神化的气质，听起来高深莫测，做起来又总像在凑公式。其实它一点都不玄。DP 就是一个非常朴素的想法：把同样的子问题算一次就够了，别反复算。所有让人头大的「状态转移方程」「滚动数组」「区间 DP」，归根结底都是围绕这一个想法在打转。

这篇文章的目标是把 DP 的解题套路彻底讲清楚。只要能回答下面三个问题，绝大多数 LeetCode 上的 DP 题你都能写出来：

1. dp[i] 到底在表示什么？（状态）
2. dp[i] 怎么从更小的答案拼出来？（转移）
3. 最小的那几个答案是什么？（边界）

后面会把这套方法套到七道经典题上：爬楼梯、打家劫舍、零钱兑换、最长递增子序列、0/1 背包、最长公共子序列、编辑距离。

为什么需要 DP：重叠子问题

上图是 fib(6) 的递归树。fib(n) = fib(n-1) + fib(n-2) 这个写法在数学上没问题，但实际跑起来 fib(2) 被算了 5 次、fib(3) 被算了 3 次。每往下一层规模就翻倍，整体复杂度是 $O(2^n)$，可真正不同的子问题只有 $n+1$ 个。

DP 做的事情就一件：第一次算出某个子问题的答案后把它存起来，下次直接拿。具体有两种写法：

• 自顶向下（记忆化）：保留递归结构，给每次调用加一层缓存。被剪掉的就是上图里那些重复的分支。
• 自底向上（表格法）：彻底放弃递归，从最小的子问题开始往大里填。

两种写法都把 $O(2^n)$ 拉到了 $O(n)$。能用 DP 的问题需要同时满足两个条件：

• 最优子结构：原问题的最优解可以由子问题的最优解组合得到。最短路径、斐波那契、背包、编辑距离都满足。
• 重叠子问题：朴素递归会反复求解同一个子问题。这正是缓存能省下时间的地方。

两个条件同时满足，DP 才有意义。只有最优子结构没有重叠（比如归并排序），缓存白加。两个都没有，得换别的范式。

三步解题套路

后面所有题都是同一个模板。多套几次，套到肌肉记忆为止。

第一步：定义状态

把 dp[i] 或 dp[i][j] 的含义写得死死的。模糊的状态定义是 DP 写错的第一大来源。能用的定义长这样：

• dp[i] = 到达第 $i$ 阶的方法数
• dp[i] = 在房屋 $0..i$ 中能偷到的最大金额
• dp[i][j] = s1[0:i] 和 s2[0:j] 的最长公共子序列长度

一个验证标准：如果我直接告诉你 dp[i-1] 和 dp[i-2] 的值是对的，你能不能写出 dp[i] 的公式？能，状态就立得住。

第二步：写状态转移

转移其实在问一件事：「在位置 $i$ 我有哪些选择？哪个最优？」 写成代码就一行，但这一行背后的思考才是 DP 的核心。

以打家劫舍为例：在第 $i$ 间房，要么偷（拿 nums[i]，但只能从 dp[i-2] 接过来），要么不偷（继承 dp[i-1]）。转移就是这两个选项取最大。

第三步：确定边界

边界是那些不需要任何递推就能直接写出答案的子问题。这一步出错，整张表都跟着错；这一步对了，剩下的格子会自己长出来。

爬楼梯：dp[0] = 1（站在地面就算一种「方法」），dp[1] = 1（爬一步到第一阶）。检验一下 dp[2] 应该是 2，而 dp[1] + dp[0] = 2，对得上，边界没问题。

一维动态规划

一维 DP 是入门的最佳场地。状态只有一个下标，转移通常只依赖前面常数个格子，套路最干净。

上图就是一维 DP 的心智模型：一排格子，每个格子从前面固定大小的窗口里推出来。理解了这张图，也就理解了为什么我们几乎总能把数组压到几个变量——你需要往回看的距离是固定的。

LeetCode 70 · 爬楼梯

楼梯有 $n$ 阶，每次可以爬 1 阶或 2 阶。问有多少种不同的爬法。

套路：

• 状态：dp[i] = 到达第 $i$ 阶的方法数
• 转移：dp[i] = dp[i-1] + dp[i-2]（最后一步要么从 $i-1$ 跨一格上来，要么从 $i-2$ 跨两格上来）
• 边界：dp[0] = dp[1] = 1

1
2
3
4
5
6
7
8

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

时间 O(n)，空间 O(n)。因为转移只用到前两个值，可以把空间压到 O(1)：

1
2
3
4
5
6
7

def climbStairs(n: int) -> int:
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

LeetCode 198 · 打家劫舍

每间房都有现金，但相邻两间不能同时偷。返回能偷到的最大金额。

套路：

• 状态：dp[i] = 考虑前 nums[0..i] 这些房屋时能偷到的最大金额
• 转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。要么跳过第 $i$ 间（沿用 dp[i-1]），要么偷（把 nums[i] 加到两间之前的最优解上）
• 边界：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def rob(nums: list[int]) -> int:
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, n):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
    return prev1

滚动后空间 O(1)。这种「选 vs 不选」的框架适用范围极广——只要在位置 $i$ 做的决策会封锁 $i-1$，状态和转移就跟打家劫舍长得一模一样。

LeetCode 322 · 零钱兑换

给定面额数组和总金额 amount，返回凑出 amount 所需的最少硬币数；凑不出返回 $-1$。

套路：

• 状态：dp[a] = 凑出金额 $a$ 所需的最少硬币数
• 转移：dp[a] = min(dp[a - c] + 1 for c in coins if c <= a)。枚举「最后一枚硬币」是哪一枚，剩下的部分由 dp[a - c] 解决
• 边界：dp[0] = 0，其他位置初始化成一个「不可能」的哨兵值

1
2
3
4
5
6
7
8
9

def coinChange(coins: list[int], amount: int) -> int:
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

时间 O(amount * len(coins))，空间 O(amount)。把哨兵设成 amount + 1 是个值得记住的小技巧——这样 min 不需要为「不可达」的状态做特殊判断。

LeetCode 300 · 最长递增子序列

求数组中最长严格递增子序列的长度。

这是第一道状态定义为「以 $i$ 结尾」而不是「考虑前缀 $0..i$」的题，差别看似细微，但很关键。

套路：

• 状态：dp[i] = 以 nums[i] 结尾的最长递增子序列长度
• 转移：dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i])，没有合法的 $j$ 时就是 $1$
• 边界：所有 dp[i] 初值都是 $1$（只包含 nums[i] 自己的子序列）
• 答案：max(dp)，最长子序列可以在任何位置结尾

1
2
3
4
5
6
7
8

def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

时间 O(n^2)。LIS 还有一个用 bisect 的 O(n log n) 写法（耐心排序），但建议先把 DP 版写熟，结构看得更清楚。

二维动态规划

只要状态需要同时记录两件事——两个字符串的位置、物品和容量、网格的行和列——就到了二维 DP 的地盘。套路完全不变，只是把「一行格子」换成「一张表」。

经典：0/1 背包

有 $n$ 件物品，第 $i$ 件重 $w_i$、价值 $v_i$；背包容量 $W$。每件物品最多选一次，求最大总价值。

图中橙色格子是示例（重量 [2,3,4,5]、价值 [3,4,5,6]、容量 $W=5$）的回溯路径。最终答案就是 dp[n][W]，沿着橙色格子往回走还能还原出选了哪些物品。

套路：

• 状态：dp[i][w] = 在前 $i$ 件物品里选，容量为 $w$ 时能得到的最大价值
• 转移：在第 $i$ 件物品上要么不选（dp[i-1][w]），要么选且能装下（dp[i-1][w - w_i] + v_i），取最大
• 边界：dp[0][w] = 0，没有物品就没有价值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]
            if w >= wi:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wi] + vi)
    return dp[n][capacity]

时间和空间都是 O(n * W)。一维空间优化版本能体现 DP 空间压缩里最容易踩坑的一个细节——容量必须逆序遍历，否则同一件物品会被重复选：

1
2
3
4
5
6
7

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    for wi, vi in zip(weights, values):
        # 逆序：dp[w - wi] 此时还是「上一行」的值
        for w in range(capacity, wi - 1, -1):
            dp[w] = max(dp[w], dp[w - wi] + vi)
    return dp[capacity]

如果改成正序，dp[w - wi] 在本轮可能已经被当前这件物品更新过——这刚好就是完全背包（每件物品可以选无限次）的递推式。完全背包本身是有用的问题，但在 0/1 背包里就是一个 bug。

LeetCode 1143 · 最长公共子序列

求两个字符串的最长公共子序列长度。

套路：

• 状态：dp[i][j] = text1[0:i] 和 text2[0:j] 的 LCS 长度
• 转移：
  • 若 text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1（沿对角线把匹配延伸一格）
  • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])（看丢哪边的字符更好）
• 边界：dp[0][j] = dp[i][0] = 0，空串和谁都没有公共子序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

时间 O(m * n)，空间 O(m * n)，可以用两行滚动数组压到 O(min(m, n))：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def longestCommonSubsequence(text1: str, text2: str) -> int:
    if len(text1) < len(text2):
        text1, text2 = text2, text1
    m, n = len(text1), len(text2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, prev
    return prev[n]

LeetCode 72 · 编辑距离

求把 word1 变成 word2 所需的最少插入 / 删除 / 替换次数。

编辑距离就是 LCS 把「选项菜单」变丰富了一点：骨架完全一样，转移多了几个分支。

套路：

• 状态：dp[i][j] = 把 word1[0:i] 变成 word2[0:j] 的最少操作次数
• 转移：
  • 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]（字符已经对上，不用动）
  • 否则取三者最小：删除 word1[i-1]（dp[i-1][j] + 1）、插入 word2[j-1]（dp[i][j-1] + 1）、替换（dp[i-1][j-1] + 1）
• 边界：dp[i][0] = i（把 word1 全删光），dp[0][j] = j（把 word2 全插进来）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # 删除
                    dp[i][j - 1],      # 插入
                    dp[i - 1][j - 1],  # 替换
                )
    return dp[m][n]

时间和空间都是 O(m * n)，同样可以用两行滚动压缩。

空间优化

空间优化的原理简单，但写对不容易。永远先问自己同一个问题：我的转移到底读了表里的哪一小块？

• 两个标量：dp[i] 只依赖 dp[i-1] 和 dp[i-2]（斐波那契、爬楼梯、打家劫舍）
• 一行数组：dp[i][j] 只依赖上一行（背包、LCS、编辑距离）。注意读的方向：正序还是逆序决定了你读到的到底是「上一行」还是「本轮已经被刷掉的当前行」
• 两行数组：既要读对角 dp[i-1][j-1] 又要读当前行时更安全。比一行版好推导一点，多用一倍内存而已

经验法则：先把 O(m * n) 版本写对，再压缩。直接奔最优空间是各种 off-by-one 和读写顺序 bug 的温床。

自顶向下 vs 自底向上

上面所有题都可以写成等价的记忆化递归版本：

1
2
3
4
5
6
7

from functools import cache

@cache
def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

什么时候用哪种：

• 记忆化递归适合递归思路最自然的题（树形 DP、博弈、状态图不规则的题）。Python 的 functools.cache 让这种写法基本零成本
• 自底向上适合需要严格控制遍历顺序的场景（要做空间压缩），或者输入很大、担心 Python 递归栈溢出时

面试时先写自底向上能传递一个信号：你考虑过遍历顺序和空间。退一步用记忆化也完全没问题。两种都能写、能互相转换，才算真正掌握。

常见 DP 类型分布图

绝大多数你会遇到的 DP 题都能塞进下面这四个篮子里：

• 线性 DP：状态只有一个下标。爬楼梯、打家劫舍、LIS、最大子数组。这类题最难的部分是选「以 $i$ 结尾」还是「考虑前缀 $0..i$」
• 二维 / 网格 DP：状态有两个下标，通常是两个字符串或者网格的行列。LCS、编辑距离、不同路径、最小路径和
• 区间 DP：状态是区间 $[i, j]$，按区间长度从小到大填。戳气球、矩阵链乘、最长回文子序列
• 状态机 DP：在位置之外多挂一两维（持有/卖出、剩余次数 $k$、奇偶、bitmask）。带冷冻期或交易次数限制的股票问题、0/1 背包、状压 DP 都是这一类

遇到新题先归类，类别基本就告诉了你状态该长什么样。

容易踩的坑

把这些写在小本本上：

• 状态太模糊：写转移时卡住，因为 dp[i] 只是「大概表示答案」。回去把定义抠紧
• 边界写错：表里的递推没问题，但起点错了一格。最快的检查方法是手算前三四个值
• **混淆「以 $i$ 结尾」和「考虑前缀 $0..i$」**：在 LIS 里这就是 max(dp)和dp[-1]` 的差别
• 一维背包遍历方向写反：正序就把 0/1 背包默默变成了完全背包
• 记忆化用了可变默认参数：def f(n, memo={}): 会让缓存在多次调用之间共享。改用 functools.cache
• 过早做空间优化：又难写又难调，白板上通常根本不需要。空间压缩留到最后

Q&A

怎么判断一道题是 DP？

关注词：「最大」「最小」「计数」「最长」「最少」。结构上看，能不能定一个决策、然后递归到一个更小的同类问题；状态空间是否小到可以缓存。如果你的第一反应是「写个分支很多的递归」，就该怀疑是 DP。

自顶向下还是自底向上？

树和不规则状态图用自顶向下，需要空间压缩用自底向上。面试中只要分析正确，两种都给满分。

状态定好了，但转移就是写不顺？

状态多半太粗了。加一维：「上一件物品有没有用过」的标记、「还能交易几次」的计数、「已经覆盖了哪些子集」的 bitmask。状态必须包含转移要用到的全部信息。

小数据对、大数据错？

大概率是这几种之一：整数溢出（C++/Java）、递归栈炸（Python）、空间压缩版本里有 bug 而二维版没有。把没压缩的版本跑一遍出错的用例对比一下。

DP 和贪心到底差在哪？

贪心做完一个局部决策就再也不回头；DP 把每一步的所有合理选择都列出来取最优，必要时会推翻之前的判断。活动选择问题贪心可解；任意面额的零钱兑换贪心就不行。

DP 一定能做空间压缩吗？

不能。压缩成立的前提是转移只读表里有界的一小块。需要回溯整张表还原最优方案的题（不只是问「最优值是多少」），就得保留完整的表。

练习路线

一个相对靠谱的 DP 练习顺序：

1. 一维热身：爬楼梯、打家劫舍、最大子数组
2. 加一维：零钱兑换、不同路径、0/1 背包
3. 双串问题：LCS、编辑距离、不同的子序列
4. 状态机：带冷冻期或 $k$ 次交易限制的股票问题
5. 区间 DP：最长回文子序列、戳气球
6. 状压 DP：旅行商、划分为 K 个相等的子集

如果一道题完全没思路，先写暴力递归。递归的状态就是 DP 的状态，递归调用的参数就是 DP 的下标。先加记忆化让它跑起来，再视情况转成表格法压缩空间。

总结

整篇文章其实只在用同一个套路解七道题：状态、转移、边界。这三件事敲定了，写代码是机械动作，复杂度分析也是顺手就出。

DP 真正难的从来不是写代码，而是给出一个精确到不需要再加任何形容词的状态定义。把时间花在那里，剩下的会自己长出来。

文章里这七道题——爬楼梯、打家劫舍、零钱兑换、LIS、0/1 背包、LCS、编辑距离——不只是练习题，它们是几乎所有更难的 DP 题最终会归约回去的模板。把这七道题彻底吃透，LeetCode 上很大一部分 Hard 标签会变成「我之前见过同款，只是换了个皮」。