LeetCode（七）：动态规划入门

动态规划在算法圈子里一直有种“高手专属”的光环，很多人觉得它复杂难懂。其实不然——DP 的核心思想特别简单：同样的子问题只算一次，别重复劳动。那些让人头疼的状态定义、转移方程和滚动优化，其实都是围绕这个核心展开的。

这篇文章的目的是帮你彻底搞明白 DP 的解题套路：只要能清晰回答下面三个问题，LeetCode 上的大部分 DP 题你都能搞定。

dp[i] 到底代表什么？（状态）
怎么用更小的答案拼出 dp[i]？（转移）
最基础的几个答案是什么？（边界）

接下来，我们将用这套方法逐一解决七道经典题目：爬楼梯、打家劫舍、零钱兑换、最长递增子序列、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] = 考虑偷前 $$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] 表示考虑前 $$i$$ 间房时能偷到的最大金额。
转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])，要么跳过第 $$i$$ 间房（沿用 dp[i-1]），要么偷这间房（加上 nums[i] 并回退到 dp[i-2]）。
边界：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)。这种「选与不选」的框架非常通用，适用于任何在位置 $$i$$ 做决策会影响 $$i-1$$ 的问题。

LeetCode 322 —— 零钱兑换#

给定硬币面额和目标金额 amount，返回凑出目标金额所需的最少硬币数；无法凑出则返回 $$-1$$ 。

解法：

状态：dp[a] 表示凑出金额 $$a$$ 所需的最少硬币数。
转移：dp[a] = min(dp[a - c] + 1 for c in coins if c <= a)，枚举最后一枚硬币的面额 $$c$$ ，剩下的部分由 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 是个实用技巧，避免对不可达状态做额外判断。

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 还有一个基于二分查找的 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，没有物品时价值为 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)。可以用一维数组优化空间，但要注意一个关键细节：容量必须逆序遍历，否则同一件物品会被重复选择。

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] 的最长公共子序列长度。
转移：
- 如果 text1[i-1] == text2[j-1]，说明当前字符匹配，dp[i][j] = dp[i-1][j-1] + 1。
- 否则，取 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（全删），dp[0][j] = j（全插）。

 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 或读写顺序的坑。

自顶向下 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 题目都可以归入以下四类，每一类都有自己的特点和解题套路：

线性 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 就不会出问题。
过早优化空间复杂度：容易出 bug，调试也麻烦，白板题更没必要。先把逻辑写对，最后再压缩空间。

常见问题#

怎么判断一个问题适合用 DP？#

看关键词：「最大」「最小」「计数」「最长」「最短」。结构上，能不能做一个决策后递归到一个更小的子问题；状态空间是否足够小，能用缓存优化。如果第一反应是写个分叉很多的递归，那大概率就是 DP 问题。

自顶向下还是自底向上更好？#

树形结构或状态图不规则时优先用自顶向下（记忆化递归），需要严格控制迭代顺序或优化空间时用自底向上（表格法）。面试中只要逻辑清晰，两种方法都能拿满分。

状态定义好了，但转移公式写不出来怎么办？#

可能是状态定义太模糊了。试着加一维：比如「上一步是否用了某个元素」「还剩几次操作」「当前覆盖了哪些子集」等。记住，状态必须包含所有影响转移的信息，否则公式很难推导。

小数据没问题，大数据出错？#

常见原因有三：

整数溢出（C++/Java 中尤其注意）。
Python 递归深度超限（栈溢出）。
空间优化版本引入了 bug，而二维版本没有。建议：先跑一遍未优化的完整版本，对比结果定位问题。

DP 和贪心算法的区别是什么？#

贪心算法一旦做出局部最优选择，就不再回头调整；DP 则会枚举每一步的所有合理选择，取最优解，甚至可能推翻之前的决策。比如活动选择问题可以用贪心解决，但任意面额的零钱兑换问题就不行。

所有 DP 都能做空间优化吗？#

不是。空间优化的前提是转移只依赖表中的有限区域。如果问题需要回溯整个 DP 表来还原最优解（而不仅仅是求最优值），就必须保留完整的表。

练习题#

DP 的学习路径可以按以下顺序展开，逐步提升难度：

一维入门：从简单的线性问题开始，比如爬楼梯、打家劫舍、最大子数组。这些题目的状态定义直观，转移方程简单，适合熟悉 DP 的基本套路。
二维扩展：在掌握一维问题后，尝试涉及两个维度的题目，例如零钱兑换、不同路径、0/1 背包。这类问题的状态通常需要同时考虑两个变量。
双串匹配：处理两个字符串或序列的问题，如最长公共子序列（LCS）、编辑距离、不同的子序列。这类问题的状态和转移方程往往围绕两个序列的索引展开。
状态机模型：引入额外的状态维度，解决更复杂的问题，比如带冷冻期或最多 $$k$$ 次交易的股票买卖问题。这类问题的状态设计需要特别注意附加条件。
区间 DP：状态与区间相关，比如最长回文子序列、戳气球。这类问题通常按照区间长度从小到大的顺序填充 DP 表。
状压 DP：使用位掩码表示状态，解决组合优化问题，比如旅行商问题、划分为 K 个相等子集。这类问题对状态压缩技巧要求较高。

遇到完全没有头绪的题目时，不妨先写一个暴力递归解法。递归函数的参数就是 DP 的状态，递归调用的逻辑就是状态转移方程。在此基础上加入记忆化优化，确保代码能跑通，最后再根据需要改写成表格法以节省空间。这种方法不仅能帮你理清思路，还能有效避免直接上手 DP 时常见的错误。

总结#

整篇文章其实只讲了一个套路，用它解了七道题：状态、转移、边界。这三件事搞定了，写代码就是个机械活儿，复杂度分析也顺带就出来了。

DP 真正的难点从来不是写代码，而是找到一个精准到不用再加修饰词的状态定义。把时间花在这上面，剩下的自然会水到渠成。

文章里的这七道题——爬楼梯、打家劫舍、零钱兑换、最长递增子序列（LIS）、0/1 背包、最长公共子序列（LCS）、编辑距离——不只是练习题，它们是模板题。几乎所有更复杂的 DP 问题，最后都能归约到这七个模型上。把这些题彻底吃透，LeetCode 上很多 Hard 题就会变成「换了个马甲，但我见过原版」。