Post

Dynamic Programming

Posted
By Yue Lin 163 min read

动态规划（Dynamic Programming, DP）是算法里最重要、也最让初学者头疼的思想之一。本文从最朴素的重复计算讲起，一步步建立 DP 的核心直觉与设计套路，再精讲一批经典 LeetCode 题，最后揭示它与强化学习之间的血缘：Bellman 方程其实就是 DP，而强化学习是它在模型未知、状态爆炸时的近似版本。

动态规划是什么：从重复计算到记忆化

动态规划（Dynamic Programming，简称 DP）大概是很多人学算法时第一个“听起来很玄”的概念。它的名字听上去很高级，但其实它背后的思想朴素得令人惊讶：把已经算过的答案存下来，下次直接拿来用，别重复劳动。 这一节我们就从最简单的斐波那契数列出发，一步一步把这个思想讲透，让你明白 DP 到底是什么、为什么它能加速、它和分治、贪心又有什么区别。

读完这一节，你应该能建立起这样一个认知：DP 不是某一个具体算法，而是一套解决问题的通用思想框架。它的核心是“用空间换时间，把子问题的答案存下来反复复用”。

先说结论：DP 不是算法，是思想

很多初学者会问：“动态规划的代码模板是什么？” 这个问题本身就有点跑偏了。DP 没有一个固定的代码模板，正如“分治”没有固定模板、“贪心”也没有固定模板一样。它们都是算法设计的范式（paradigm），是一类解题思路的统称。

DP 的本质可以浓缩成一句话：

把一个大问题拆成若干个互相重叠的小问题，每个小问题只算一次、把答案记下来，后面需要时直接查表，从而避免大量重复计算。

注意这句话里有两个关键词：拆成小问题（这要求问题有结构）、互相重叠（这是 DP 能省时间的前提）。这两点正好对应 DP 的两大基石，下面我们逐个来看。

DP 的两大基石

一个问题能用 DP 解决，通常需要同时满足两个条件。

第一块基石：最优子结构（Optimal Substructure）

“最优子结构”的意思是：一个问题的最优解，可以由它的子问题的最优解组合（推导）出来。换句话说，大问题的答案“建立在”小问题答案之上。

举个生活化的例子。你要从北京开车到广州，走的是一条最短路线。如果这条最短路线途经武汉，那么从北京到武汉的这一段，一定也是北京到武汉的最短路线。为什么？因为如果存在一条更短的北京到武汉的路，那把它替换进去，整条北京到广州的路就会更短，这就和“原路线是最短的”矛盾了。

这就是最优子结构：大问题（北京到广州最短路）的最优解，包含了子问题（北京到武汉最短路）的最优解。正因为有这种“层层嵌套的最优性”，我们才能从小问题的答案一步步推出大问题的答案。

第二块基石：重叠子问题（Overlapping Subproblems）

“重叠子问题”的意思是：在递归求解的过程中，同一个子问题会被反复求解很多次。

这正是 DP 能“加速”的根本原因。如果子问题各不相同、互不重叠，那存下来也没意义（反正每个只算一次）；只有当同一个子问题被反复需要时，“把答案存下来下次直接查”才真正省下了大量时间。

这两块基石的关系可以这样理解：

  • 最优子结构保证了 DP 的正确性（大问题能由小问题正确地推出来）。
  • 重叠子问题保证了 DP 的高效性（存下来复用才有意义）。

第三个概念：无后效性（No Aftereffect）

还有一个常常被忽略但很重要的性质，叫无后效性。它的意思是：

当我们已经确定了某个子问题（某个状态）的答案后，这个答案就固定不变了，它只取决于“如何到达这个状态”的结果，而不取决于“将来会怎么走”。未来的决策不会反过来修改过去已经算好的状态。

换个说法：状态 $i$ 的值一旦算出来，就是定论。后面计算状态 $i+1$、$i+2$ 时，可以放心地引用状态 $i$ 的值，不用担心它会被“回头改掉”。

无后效性是 DP 能“按顺序填表”的前提。如果一个问题不满足无后效性（比如未来的选择会反过来影响过去的状态值），那它就不能简单地用 DP 的方式按部就班地推导。绝大多数标准 DP 题目天然满足这个性质，所以初学时不必太纠结，但要知道它的存在。

用斐波那契数列把三个阶段走一遍

讲完抽象概念，我们用最经典的例子，斐波那契数列，来把 DP 的思想具体化。斐波那契数列的定义大家都熟悉：

\[F(0) = 0,\quad F(1) = 1,\quad F(n) = F(n-1) + F(n-2)\ (n \ge 2)\]

也就是 $0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots$ 每一项都等于前两项之和。

这个递推式本身就已经体现了最优子结构的雏形：$F(n)$ 完全由 $F(n-1)$ 和 $F(n-2)$ 决定。下面我们用三种不同的方式来计算它，亲眼看看 DP 思想是怎么一步步让效率从指数级降到线性级的。

阶段一：朴素递归（暴力，复杂度约 $2^n$）

最直接的写法就是照着定义递归：

1
2
3
4
5
6

def fib(n: int) -> int:
    # 递归基（base case）：n 为 0 或 1 时直接返回
    if n < 2:
        return n
    # 递归式：直接照搬定义 F(n) = F(n-1) + F(n-2)
    return fib(n - 1) + fib(n - 2)

这段代码非常符合直觉，逻辑也完全正确。但它有一个致命问题：慢得离谱。我们来画出 fib(5) 的递归树，看看到底发生了什么。

1
2
3
4
5
6
7
8
9

                          fib(5)
                  /                    \
              fib(4)                  fib(3)
            /        \              /        \
        fib(3)      fib(2)      fib(2)      fib(1)
       /     \     /    \      /    \
   fib(2)  fib(1) fib(1) fib(0) fib(1) fib(0)
   /    \
fib(1) fib(0)

仔细数一数这棵树，你会发现严重的重复计算：

  • fib(3) 被算了 2 次
  • fib(2) 被算了 3 次
  • fib(1) 被算了 5 次
  • fib(0) 被算了 3 次

n 才等于 5，重复就已经如此夸张。当 n 变大时，这棵树会爆炸式生长。每个非叶子节点都会分裂成两个子节点，整棵树的节点数大约是 $2^n$ 量级，所以时间复杂度约为 $O(2^n)$（更精确地说，节点数和 $F(n)$ 同阶，约为 $1.618^n$，黄金分割比的幂次，但量级上依旧是指数级）。

这就是问题所在：同一个子问题 fib(2)、fib(3) 被反复求解了无数次。 这恰恰说明斐波那契问题具有强烈的重叠子问题特性，而这，正是 DP 能大显身手的信号。

阶段二：记忆化搜索（Memoization，自顶向下 top-down，复杂度 $O(n)$）

既然问题出在“同一个子问题被反复计算”，那解决办法呼之欲出：算过的就记下来，下次直接查，不再重算。 这个技巧就叫记忆化（memoization）。

我们准备一个“备忘录”（通常是数组或哈希表），每算出一个 fib(k) 就把它存进去。下次再要 fib(k) 时，先查备忘录：如果有，直接返回；如果没有，才真正去递归计算，并把结果存好。

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

def fib(n: int) -> int:
    memo = {}  # 备忘录：存放已经算过的子问题答案

    def helper(k: int) -> int:
        # 递归基
        if k < 2:
            return k
        # 关键一步：先查备忘录，算过就直接返回，避免重复计算
        if k in memo:
            return memo[k]
        # 没算过才真正递归计算
        result = helper(k - 1) + helper(k - 2)
        # 算完立刻存入备忘录，供以后复用
        memo[k] = result
        return result

    return helper(n)

加上这个备忘录后会发生什么？再回头看那棵递归树：当我们第二次需要 fib(3) 时，它已经在备忘录里了，于是这一整棵子树直接被剪掉，瞬间返回结果，不再展开。

这样一来，每个不同的子问题 fib(0) 到 fib(n) 都只会被真正计算一次，总共 $n+1$ 个子问题，所以时间复杂度降到了 $O(n)$。从指数级到线性级，这是一个天壤之别的飞跃：当 $n = 50$ 时，朴素递归要算约 $10^{10}$ 次（要等很久），而记忆化只需约 50 次（一瞬间）。

这种“从大问题出发，递归往下拆，遇到算过的就查表”的方式，叫做自顶向下（top-down）。它保留了递归的写法（贴近问题定义、好理解），同时用备忘录消除了重复计算。

Python 小贴士：标准库里有现成的工具 functools.lru_cache，加一个装饰器就能自动帮你做记忆化，连备忘录都不用手写：

1
2
3
4
5
6
7

from functools import lru_cache

@lru_cache(maxsize=None)  # 自动缓存每次调用的结果
def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

它的内部原理和我们手写的备忘录完全一样。学习阶段建议先手写一遍理解透彻，再用这个偷懒。

阶段三：递推填表（Tabulation，自底向上 bottom-up，复杂度 $O(n)$）

记忆化是“从上往下、用到才算”。我们还可以反过来思考：既然 fib(n) 依赖 fib(n-1) 和 fib(n-2)，那我干脆从最小的开始，一个一个往上算，等算到 fib(n) 时，它需要的两个值早就准备好了。这种方式叫自底向上（bottom-up），也叫递推填表（tabulation）。

我们用一个数组 dp 来当这张“表”，dp[i] 就表示 $F(i)$ 的值，然后按 $i$ 从小到大的顺序把表填满：

1
2
3
4
5
6
7
8
9
10
11

def fib(n: int) -> int:
    if n < 2:
        return n
    # dp[i] 表示斐波那契数列的第 i 项，即 F(i)
    dp = [0] * (n + 1)
    dp[0] = 0  # 边界：F(0) = 0
    dp[1] = 1  # 边界：F(1) = 1
    # 从小到大填表，每一项都依赖前面已经填好的两项
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # 状态转移方程
    return dp[n]

这里出现了 DP 中最核心、最需要写清楚的东西，状态转移方程（state transition equation）：

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

配套的还有边界条件（base case）：

\[dp[0] = 0,\quad dp[1] = 1\]

“状态转移方程”听上去很唬人，其实它就是在回答一个问题：当前这个状态的答案，怎么由前面已经算好的状态推出来？ 对斐波那契来说，答案就是“等于前两项之和”。写 DP 题时，找出正确的状态定义和转移方程，往往就是整道题最关键的一步。

填表过程一目了然，比如 $n = 6$：

1
2

i      0    1    2    3    4    5    6
dp[i]  0    1    1    2    3    5    8

从左往右一格一格填，每一格只看它左边两格，绝不回头。这个过程完美体现了前面讲的无后效性：dp[2] 一旦填好就是 1，后面算 dp[3]、dp[4] 时都放心地引用它，它永远不会被改回去。

这种写法同样是每个子问题只算一次，所以时间复杂度也是 $O(n)$。它和记忆化在效率上是同一量级，区别只在于“思考方向”：记忆化是自顶向下（从 n 往 0 拆），递推是自底向上（从 0 往 n 推）。

进阶：空间优化到 $O(1)$

填表法还有一个记忆化做不到的好处：容易做空间优化。

观察转移方程 $dp[i] = dp[i-1] + dp[i-2]$，你会发现：算 dp[i] 时，我们只用得到前两项，更早的 dp[0]、dp[1]、dp[3] 全都用不上了。既然如此，何必保存整个数组？只需要两个变量滚动着用就行：

1
2
3
4
5
6
7
8
9
10

def fib(n: int) -> int:
    if n < 2:
        return n
    prev2 = 0  # 相当于 dp[i-2]，初始为 F(0)
    prev1 = 1  # 相当于 dp[i-1]，初始为 F(1)
    for _ in range(2, n + 1):
        cur = prev1 + prev2      # 当前项 = 前两项之和
        prev2 = prev1            # 向前滚动：旧的 prev1 变成新的 prev2
        prev1 = cur              # 向前滚动：刚算出的 cur 变成新的 prev1
    return prev1

现在我们只用了 prev1、prev2、cur 三个变量，无论 n 多大，占用的空间都是固定的，所以空间复杂度从 $O(n)$ 降到了 $O(1)$。这种“只保留必要的几个状态、滚动复用”的技巧，叫做滚动变量（滚动数组），是 DP 空间优化里最常用的手法之一。

把三种解法放在一起对比，你就能清晰看到 DP 思想带来的提升：

解法思考方向时间复杂度空间复杂度关键点
朴素递归自顶向下$O(2^n)$$O(n)$（递归栈）大量重复计算
记忆化搜索自顶向下$O(n)$$O(n)$算过就存，查表复用
递推填表自底向上$O(n)$$O(n)$从小到大顺序填表
滚动优化自底向上$O(n)$$O(1)$只保留前两个状态

这张表其实就是整个 DP 学习路线的缩影：先看到重复计算（朴素递归），再用存储消除重复（记忆化 / 填表），最后压缩空间（滚动）。 几乎每一道 DP 题，你都可以按这个路径去思考。

动手练一练：LeetCode 上的同款题

斐波那契的思想可以原封不动地搬到一道入门 DP 题上：

  • LeetCode 70. 爬楼梯（Climbing Stairs）：你在爬楼梯，每次可以爬 1 级或 2 级，问爬到第 $n$ 级共有多少种不同的走法。

它的状态转移方程是：

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

是不是和斐波那契一模一样？因为：到达第 $i$ 级的最后一步，要么是从第 $i-1$ 级跨 1 步上来，要么是从第 $i-2$ 级跨 2 步上来，所以总走法数等于这两种情况之和。这正是“用最优子结构 + 状态转移”分析问题的典型套路。

其他几道适合入门的同类题（都建立在同一个思想上）：

  • LeetCode 509. 斐波那契数（Fibonacci Number）：本节内容的直接对应题。
  • LeetCode 746. 使用最小花费爬楼梯（Min Cost Climbing Stairs）：在爬楼梯基础上加了“代价最小化”，让你第一次接触“求最优值”型的 DP。
  • LeetCode 1137. 第 N 个泰波那契数（N-th Tribonacci Number）：递推从“前两项之和”变成“前三项之和”，练习改造状态转移方程。

DP 与分治、贪心的区别

最后，我们把 DP 和另外两个常见的算法范式放在一起对比，帮你彻底厘清边界。这三者都涉及“把问题拆开”，但拆法和复用方式各不相同。

DP 与分治（Divide and Conquer）的区别

分治也是“把大问题拆成小问题、分别解决、再合并”，比如归并排序、快速排序。它和 DP 看起来很像，关键区别在于：

  • 分治的子问题通常是互相独立、互不重叠的。比如归并排序把数组切成左右两半，左半边和右半边各排各的，毫无交集，所以没有重复计算的问题，自然也不需要存表。
  • DP 的子问题是互相重叠的（这正是 DP 的第二块基石）。同一个子问题会被反复需要，所以必须把答案存下来复用。

一句话总结：有重叠子问题、需要存表复用的，才是 DP；子问题互相独立、各算各的，那是分治。 你完全可以把 DP 理解成“专门针对重叠子问题做了优化的分治”。

DP 与贪心（Greedy）的区别

贪心算法每一步都只看眼前，选当前看起来最好的那个选项，并且绝不反悔，期望这样一路走到底就能得到全局最优。

  • 贪心靠的是“局部最优能导出全局最优”这个性质（贪心选择性质），它不回头、不考虑全部可能，所以又快又省，但并不是所有问题都成立，用错了就会得到错误答案。
  • DP 则会系统地考察所有相关的子问题，通过比较、组合子问题的答案来保证拿到的是真正的全局最优。它比贪心“想得更全”，代价是更多的计算和存储。

一句话总结：贪心是“赌”局部最优能拼出全局最优、一条路走到黑；DP 是“稳”，把该考虑的子问题都考虑到、再择优组合。 当你不确定贪心是否正确时，DP 往往是更保险的选择。

本节小结

把这一节的核心要点再收束一下：

  1. DP 是一种思想，不是某个具体算法，核心是“用空间换时间，把子问题答案存下来反复复用”。
  2. 能用 DP 的问题要满足最优子结构（保证正确）和重叠子问题（保证高效），通常还伴随无后效性（保证能顺序推导）。
  3. 从朴素递归（$O(2^n)$，大量重复）到记忆化搜索（$O(n)$，自顶向下查表）再到递推填表（$O(n)$，自底向上填表），直至滚动优化（$O(1)$ 空间），这条路径是分析几乎所有 DP 题的通用思考框架。
  4. 状态定义和状态转移方程是 DP 的灵魂，写题时务必把它们想清楚、写明白。
  5. DP 与分治的分水岭是“子问题是否重叠”；与贪心的分水岭是“是否系统考察所有子问题以保证全局最优”。

地基打好了，后面我们就可以在这套思想的基础上，去攻克背包、区间、树形等各种更复杂的 DP 模型了。

动态规划的设计套路：五步法

很多人觉得动态规划（Dynamic Programming，简称 DP）难，其实不是它本身有多玄，而是缺一套可复制的、机械的思考流程。一旦你有了流程，绝大多数 DP 题都能按部就班地拆下来。这一节我们就把这套流程讲透，叫它五步法。

请先记住一句话：DP 的全部困难，几乎都集中在“第一步：定义状态”。 状态定义对了，后面四步往往水到渠成；状态定义错了，后面再怎么努力都是死路。所以本节会把第一步讲得格外细。

下面先给出五步法的总览，再逐步深入。

五步法总览

  1. 定义状态：明确 dp 数组每一维代表什么，以及 dp[…] 这个值本身代表什么（是“最值”还是“方案数”还是“是否可行”）。
  2. 推导状态转移方程（recurrence）：从更小的子问题如何拼出当前问题，写成一个等式。
  3. 确定初始条件与边界（base case）：哪些状态不依赖别人、可以直接填，以及越界处理。
  4. 确定计算顺序（填表方向）：保证算每个状态时，它依赖的子问题都已经算好。
  5. 定位最终答案：答案到底落在哪个状态上（是 dp[n]？dp[n][m]？还是全表的最大值？）。

我们用一道最简单的题贯穿讲解，再扩展到更典型的二维题。

先用一道入门题走一遍五步法

题目：LeetCode 70.「爬楼梯」（Climbing Stairs）。你每次可以爬 1 阶或 2 阶，问爬到第 $n$ 阶共有多少种不同方法。

第一步：定义状态。 我们问自己一个问题：要描述“爬到第几阶有多少种走法”，需要几个变量？显然只需要“当前在第几阶”这一个变量。于是定义：

\[dp[i] = \text{爬到第 } i \text{ 阶的不同方法数}\]

注意这句话要“咬文嚼字”般精确。它的含义是：从第 0 阶出发，恰好停在第 $i$ 阶，路径有几条。把这句话写在纸上，后面每一步都以它为唯一依据。

第二步：推导状态转移方程。 想象你正站在第 $i$ 阶。你的上一步只可能来自两个地方：从第 $i-1$ 阶迈 1 步上来，或从第 $i-2$ 阶迈 2 步上来。这两种来路互不重叠、也没有遗漏，所以方法数直接相加：

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

这就是 recurrence。它的本质是：当前问题的解 = 若干个更小子问题的解的组合。

第三步：初始条件与边界。 转移方程要用到 $dp[i-1]$ 和 $dp[i-2]$，所以最小的两个 $i$ 没法靠方程算出来，必须手工给定：

\[dp[0] = 1,\quad dp[1] = 1\]

$dp[0]=1$ 的解释是：站在起点不动，算作“一种方法（空走法）”。$dp[1]=1$ 表示爬到第 1 阶只有一种走法。base case 一定要从状态定义出发去验证，而不是凭感觉填。

第四步：计算顺序。 $dp[i]$ 依赖比它小的 $i-1$ 和 $i-2$，所以只要从小到大填表即可（$i$ 从 2 递增到 $n$）。这样轮到算 $dp[i]$ 时，它需要的两个子问题一定早就算好了。

第五步：最终答案。 我们要的是“爬到第 $n$ 阶”，正好就是 $dp[n]$。

把五步翻译成代码：

1
2
3
4
5
6
7
8

def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1
    dp = [0] * (n + 1)          # dp[i]：爬到第 i 阶的方法数
    dp[0], dp[1] = 1, 1         # base case
    for i in range(2, n + 1):   # 从小到大填表（计算顺序）
        dp[i] = dp[i - 1] + dp[i - 2]   # 状态转移方程
    return dp[n]                # 最终答案

看，五步法的每一步都对应代码里清清楚楚的一块。这就是它的价值：把“灵感”变成“流程”。

第一步：定义状态（最难、最关键，单独深讲）

为什么说定义状态最难？因为它要求你“反向”思考：先假设答案的某个零件已经被解出来了，再去描述这个零件是什么。下面给出几条实操经验。

（一）状态要包含“做决策所需的全部信息”，不多不少。

一个好状态的检验标准是：站在这个状态上，你能不能仅凭它就决定“下一步怎么走”或“上一步从哪来”，而不需要回头看历史路径。这正是“无后效性”（见后文）。如果发现光靠当前几维信息还不够决策，说明状态维度漏了，要补维。

举例：LeetCode 322.「零钱兑换」（Coin Change），硬币面额数组 coins、目标金额 amount，求凑出 amount 的最少硬币数。决策是“再选一枚什么面额的硬币”。要做这个决策，我只需要知道“还差多少钱”。于是：

\[dp[a] = \text{凑出金额 } a \text{ 所需的最少硬币数}\]

只需一维就够了。注意值的含义是“最少硬币数”，是一个最值。

（二）数组的“每一维”和“那个值”是两件事，都要交代清楚。

很多初学者只说“dp[i][j] 是答案”，这是错误的。必须分别说明：

  • 每一维下标的含义：比如 $i$ 表示“考虑前 $i$ 个物品”，$j$ 表示“背包剩余容量为 $j$”。
  • dp 值本身的含义：比如“在前 $i$ 个物品、容量 $j$ 的限制下能装的最大价值”。

举例：LeetCode 1143.「最长公共子序列」（Longest Common Subsequence），给两个字符串 text1、text2。

\[dp[i][j] = \text{text1 的前 } i \text{ 个字符与 text2 的前 } j \text{ 个字符的最长公共子序列长度}\]

这里 $i$、$j$ 是“前缀长度”，dp 值是“最长公共子序列长度”。一句话把三件事（两维含义 + 值含义）全说清。

（三）“前 i 个”通常比“以 i 结尾”更好想，但两者各有用武之地。

这是一个非常实用的区分，初学者一定要分清这两种常见状态范式：

  • 前缀型：“考虑前 $i$ 个元素”。它把整个集合一刀切成“已处理 / 未处理”两半，转移时只关心“第 $i$ 个选不选”。背包、LCS、编辑距离都属于这一类。
  • 结尾型：“以第 $i$ 个元素结尾”。它要求子结构必须用上第 $i$ 个元素。求“连续 / 不可断开”的子结构时往往要用它。

经典反例对比：LeetCode 53.「最大子数组和」（Maximum Subarray）。如果你定义“前 $i$ 个元素的最大子数组和”，会发现转移写不出来，因为子数组要求连续，“前 $i$ 个的答案”无法直接拼出“前 $i+1$ 个的答案”。改用结尾型就通了：

\[dp[i] = \text{以 nums}[i] \text{ 结尾的最大连续子数组和}\] \[dp[i] = \max(nums[i],\ dp[i-1] + nums[i])\]

含义是：以 $i$ 结尾的最大和，要么就是 $nums[i]$ 自己单独成段，要么是把前面“以 $i-1$ 结尾的最优段”接上来。最终答案不是 $dp[n-1]$，而是整张表的最大值 $\max_i dp[i]$（因为最优子数组可以结尾在任意位置）。这正好说明第五步“定位答案”并不总是表的最后一格，要回到状态定义去想。

（四）状态定义错了的典型信号。 如果你在写转移方程时，发现“必须知道某个状态定义里没记录的信息才能转移”，那不是转移难，而是状态漏维了，回去补。转移写不顺，九成是状态没定义好。

第二步：推导状态转移方程

转移方程的核心思想只有一句：把“当前这个大问题”拆成“对最后一步的若干种决策”，每种决策都落回一个更小的、已经定义好的子问题。

操作模板：盯住状态定义里“最后那一步 / 最后那个元素”，穷举它的所有可能取法，每种取法对应一个子问题。

以 LeetCode 322.「零钱兑换」为例，盯住“最后选的那一枚硬币”。如果最后那枚硬币面额是 $c$（来自 coins），那么在它之前已经凑好了金额 $a-c$，所需硬币数是 $dp[a-c]$，再加上这最后 1 枚：

\[dp[a] = \min_{c \in coins,\ c \le a} \big( dp[a-c] + 1 \big)\]

如果凑不出（所有 $dp[a-c]$ 都是“无穷大”），则 $dp[a]$ 保持无穷大表示无解。注意：

  • 求最值用 $\min$ / $\max$。
  • 求计数用求和（如爬楼梯的 $+$）。
  • 求可行性用逻辑或（如下例的子集和，能凑出就是 True）。

代码：

1
2
3
4
5
6
7
8
9

def coin_change(coins: list[int], amount: int) -> int:
    INF = float("inf")
    dp = [INF] * (amount + 1)   # dp[a]：凑出金额 a 的最少硬币数
    dp[0] = 0                   # base case：凑出 0 元需 0 枚
    for a in range(1, amount + 1):
        for c in coins:                 # 穷举"最后一枚硬币"的面额
            if c <= a and dp[a - c] != INF:
                dp[a] = min(dp[a], dp[a - c] + 1)   # 转移：取最少
    return dp[amount] if dp[amount] != INF else -1  # 最终答案

二维转移的推导（以 LCS 为例）。 当有两个维度时，盯住“两个序列各自的最后一个元素”。对 $dp[i][j]$（text1 前 $i$ 个与 text2 前 $j$ 个的 LCS 长度），讨论 text1 的第 $i$ 个字符和 text2 的第 $j$ 个字符是否相等：

  • 若 $\text{text1}[i-1] = \text{text2}[j-1]$（下标从 0 开始，故第 $i$ 个字符是 index $i-1$），这两个字符可以一起配进公共子序列，长度在 $dp[i-1][j-1]$ 基础上 $+1$。
  • 若不相等，则这两个字符不可能同时是配对的末尾，至少舍弃其中一个，取两种舍弃方式中较优的：
\[dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{text1}[i-1] = \text{text2}[j-1] \\ \max\big(dp[i-1][j],\ dp[i][j-1]\big), & \text{否则} \end{cases}\]
1
2
3
4
5
6
7
8
9
10
11

def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    # dp[i][j]：text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度
    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]   # 最终答案

第三步：确定初始条件与边界（base case）

base case 是那些不依赖任何子问题、可以直接写出答案的状态。它们是整个递推的“地基”，地基错了整栋楼塌。两条原则：

（一）base case 要从状态定义反推，而不是拍脑袋。 在 LCS 里，$dp[0][j]$ 的含义是“text1 取 0 个字符与 text2 前 $j$ 个的 LCS 长度”。空串与任何串的公共子序列长度必为 0，所以 $dp[0][j]=0$、$dp[i][0]=0$。代码里我们用 [[0]*(n+1) ...] 把第 0 行第 0 列全初始化成 0，正好就是这件事。

（二）边界是指“下标越界”的处理。 比如爬楼梯里 $dp[i-2]$ 在 $i<2$ 时会越界，所以我们专门给了 $dp[0]$、$dp[1]$。零钱兑换里 if c <= a 就是在防止 $dp[a-c]$ 下标变负。多预留一行一列（用 $n+1$ 而非 $n$ 长度）是处理边界的常见技巧，它能让“空前缀”自然成为下标 0，省去很多 if 判断。

第四步：确定计算顺序（填表方向）

铁律只有一条：算某个状态时，它在转移方程里用到的所有子问题都必须已经被算出来。

怎么定方向？看转移方程里“箭头指向哪里”：

  • 爬楼梯 $dp[i]$ 依赖 $dp[i-1],dp[i-2]$（更小的下标）→ $i$ 从小到大。
  • LCS $dp[i][j]$ 依赖 $dp[i-1][j]$、$dp[i][j-1]$、$dp[i-1][j-1]$（都在它的上方或左方）→ 按行从上到下、每行从左到右遍历，正好保证这三个方向的格子先于当前格被填好。

如果你的转移依赖“更大下标”的状态（例如区间 DP 里 $dp[i][j]$ 依赖 $dp[i+1][j]$），那就要反向遍历（$i$ 从大到小）。判断方法永远一样：在纸上画出依赖箭头，确保被依赖者先算。这一步本质是给状态做一次“拓扑排序”，让每个状态都排在它依赖的状态之后。

第五步：定位最终答案

写完表别急着返回 $dp[n]$。回到第一步的状态定义，问：“我要的那个答案，对应表里哪一格？”常见三种情况：

  • 答案就是“全部处理完”的那一格：如爬楼梯返回 $dp[n]$、LCS 返回 $dp[m][n]$、零钱返回 $dp[amount]$。
  • 答案是整张表的极值：如最大子数组和（结尾型）返回 $\max_i dp[i]$，因为最优解可结尾在任意位置。
  • 答案需要再做一次判断或换算：如零钱兑换里，若 $dp[amount]$ 仍是无穷大，要换算成 $-1$ 表示无解。

把第五步单独列出来，就是为了防止“表填对了，最后一行 return 写错”这种功亏一篑的低级错误。

如何识别一道题适合用 DP？

不是所有题都该上 DP。判断一道题是否是 DP，看它是否同时满足下面这组特征。

（一）问题类型属于这三类之一（这是强信号）：

  • 求最值：最长 / 最短 / 最大 / 最小 / 最优。例：最长公共子序列、最少硬币数。
  • 求计数：有多少种方案 / 路径 / 排列。例：爬楼梯的方法数、不同路径数。
  • 求可行性：能否 / 是否存在某种方案。例：LeetCode 416.「分割等和子集」（Partition Equal Subset Sum），问能否把数组分成两个和相等的子集。

（二）具有“最优子结构”： 大问题的最优解，可以由子问题的最优解拼出来。爬楼梯到第 $i$ 阶的方法数，正好由到 $i-1$、$i-2$ 阶的方法数拼出，这就是最优子结构。如果一个问题的整体最优没法用局部最优拼出（局部最优拼起来反而更差），那它就不适合 DP，可能要用贪心反例去排除，或干脆用搜索。

（三）具有“重叠子问题”： 用朴素递归去解时，同一个子问题会被反复计算很多次。这是 DP 区别于普通分治的关键。以爬楼梯的朴素递归为例，f(n) 会调用 f(n-1) 和 f(n-2)，而 f(n-1) 又会调用 f(n-2)，于是 f(n-2) 被算了不止一次，越往下重复越爆炸（这棵递归树的规模是指数级的）。DP 的全部省时间，就来自“把每个子问题只算一次、存起来复用”。如果子问题互不重叠（每个只出现一次），那 DP 退化成普通分治，用不用 DP 都一样，比如归并排序就不是 DP。

（四）具有“无后效性”： 一旦某个状态的值确定下来，它不会再被未来的决策修改；换句话说，未来只依赖“当前状态是什么”，而不依赖“你是经由哪条具体路径到达这个状态的”。这正是第一步里强调的“状态要包含做决策的全部信息”。无后效性破坏的典型例子：如果一道题里“先走 A 再走 B”和“先走 B 再走 A”会导致后续可选项不同，而你的状态又没把这种差异记进去，那它就有后效性，当前的状态定义不可用，要么补维，要么换思路。

一句话口诀：看到“求最值 / 计数 / 可行性”，又能拆成“会重复出现且无后效性的子问题”，就八成是 DP。

两种实现风格：自顶向下（记忆化）vs 自底向上（递推）

DP 有两种写法，它们解决的是同一组子问题，只是“谁先算”的顺序不同。

（一）自顶向下 + 记忆化（Top-Down Memoization）。 保持递归的写法（从大问题往小问题递归），但用一个缓存（数组或哈希表）记下每个子问题的答案，再次遇到同一子问题时直接返回，避免重复计算。

以爬楼梯为例：

1
2
3
4
5
6
7
8
9

from functools import lru_cache

def climb_stairs_memo(n: int) -> int:
    @lru_cache(maxsize=None)        # 自动缓存每个子问题的结果
    def f(i: int) -> int:
        if i <= 1:                  # base case
            return 1
        return f(i - 1) + f(i - 2)  # 与转移方程完全对应
    return f(n)

@lru_cache 帮我们做了记忆化。也可以手写一个 memo 数组，效果一样。

（二）自底向上 + 递推（Bottom-Up Tabulation）。 就是本节前面那种写法：先填最小的 base case，再按计算顺序一格一格往上推，用循环代替递归。

1
2
3
4
5
6
7
8

def climb_stairs_tab(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]

两者怎么选？ 对比如下：

维度自顶向下（记忆化递归）自底向上（递推）
思维直觉更贴近“问题怎么拆”，照着转移方程写即可，容易上手需要先想清楚“填表顺序”，门槛略高
计算范围只算真正用到的子问题（按需计算），状态空间稀疏时更省通常会把整张表都填满，哪怕有些格子用不到
运行开销有函数调用开销，深递归可能爆栈纯循环，常数更小，无爆栈风险
空间优化难以做“滚动数组”压缩容易做空间压缩（见下）
调试递归栈，调试稍麻烦表是显式的，便于打印观察

实战建议：先用自顶向下把转移方程验证对（因为它最像你脑子里的拆解过程），思路通了之后，如果需要更高性能或要做空间优化，再翻译成自底向上。两者得到的答案必然一致，因为它们求的是同一组子问题。

附：空间压缩的直觉。 自底向上时，如果发现 $dp[i]$ 只依赖前面常数个状态（如爬楼梯只用 $dp[i-1]$、$dp[i-2]$），就不必存整个数组，用两三个变量滚动即可，把 $O(n)$ 空间降到 $O(1)$：

1
2
3
4
5
6
7

def climb_stairs_o1(n: int) -> int:
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1             # 分别代表 dp[i-2]、dp[i-1]
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2   # 滚动更新
    return prev1

这种“只保留必要历史”的压缩，几乎只在自底向上写法里方便实现，这也是它的一大优势。

本节小结

五步法是一套可机械执行的流程：定义状态 → 写转移方程 → 定 base case → 定计算顺序 → 定位答案。其中定义状态是命门，记住“状态要装下做决策所需的全部信息，且无后效性”。识别 DP 题就盯三类目标（最值 / 计数 / 可行性）加两个性质（重叠子问题 + 无后效性 + 最优子结构）。实现时先用记忆化把方程跑通，再按需翻成递推并做空间压缩。把这套流程练成肌肉记忆，DP 就从“灵感题”变成“流程题”。

经典题精讲（一）：一维 DP

学会了 DP 的基本套路之后，最好的内功修炼方式就是反复打磨几道经典题。本节挑选了四道一维 DP 的代表作。所谓“一维”，指的是我们用来描述状态的“自由变量”只有一个（通常就是一个下标 $i$），所以 dp 数组是一维的。

我会对每道题都使用完全相同的六步结构来拆解：状态定义 → 转移方程 → 初始化 → Python 代码 → 复杂度 → 空间优化（滚动变量）。请注意，重点不在于记住答案，而在于体会“为什么状态要这样定义”“转移方程是怎么一步步想出来的”。当你能独立复现这套推导，一维 DP 就算真正过关了。

在开始之前，先记住一句贯穿全节的口诀：状态定义决定一切。状态定义对了，转移方程往往自然浮现；状态定义错了（或定义得含糊），整道题就会卡死。所以每道题我都会花最多笔墨在“状态定义”这一步。

一、爬楼梯（70, Climbing Stairs / 爬楼梯）

题目：假设你正在爬楼梯，需要爬 $n$ 阶才能到达楼顶。每次你可以爬 1 个或 2 个台阶。问有多少种不同的方法可以爬到楼顶。

1. 状态定义

这是入门 DP 的“Hello World”。我们要数“方法数”，所以自然想到让状态值就是方法数。

设 $dp[i]$ 表示“爬到第 $i$ 阶台阶，一共有多少种不同的走法”。

这里的“自由变量”只有一个：当前所处的台阶编号 $i$，所以是一维 DP。我们的目标答案就是 $dp[n]$。

为什么这样定义？因为 DP 的核心是“用子问题的解拼出大问题的解”。爬到第 $n$ 阶的方法，一定可以由“爬到更靠下的某些台阶的方法”组合而来。把“爬到第 $i$ 阶”作为子问题，子问题之间就能建立递推关系。

2. 转移方程

现在思考最关键的一步：站在第 $i$ 阶往回看，我上一步是从哪儿来的？

题目规定每次只能爬 1 阶或 2 阶，所以到达第 $i$ 阶的“最后一步”只有两种可能：

（1）从第 $i-1$ 阶迈 1 步上来； （2）从第 $i-2$ 阶迈 2 步上来。

这两种情况是互斥的（最后一步要么是 1 阶要么是 2 阶，不会同时发生），而且涵盖了所有可能。根据加法原理，把两类方法数相加即可：

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

是不是很眼熟？这正是斐波那契数列的递推式。

请特别体会这里的思维方式：我们不去关心“前面那一大串路是怎么走的”，只关心“最后一步从哪来”。因为“走到第 $i-1$ 阶的所有走法”已经被 $dp[i-1]$ 完整封装好了，我们直接拿来用就行。这种“只盯最后一步”的视角，是几乎所有 DP 题的通用突破口。

3. 初始化

递推式需要两个起点 $dp[i-1]$ 和 $dp[i-2]$，所以必须先把最小的两项手工确定，否则递推无从开始。

$dp[1] = 1$：爬到第 1 阶只有一种方法（迈 1 步）。 $dp[2] = 2$：爬到第 2 阶有两种方法（1+1，或者直接 2）。

如果你愿意用 $dp[0]$，可以定义 $dp[0] = 1$，表示“待在原地（爬 0 阶）算 1 种空走法”。这样 $dp[1]=dp[0]=1$、$dp[2]=dp[1]+dp[0]=2$ 也能自洽。初学者用 $dp[1]$、$dp[2]$ 起步更直观，下面代码就这么写。

4. Python 代码

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

def climbStairs(n: int) -> int:
    # 边界：只有 1 阶时，直接返回 1 种走法
    if n <= 2:
        return n

    # dp[i] 表示爬到第 i 阶的走法数
    dp = [0] * (n + 1)
    dp[1] = 1  # 第 1 阶：1 种
    dp[2] = 2  # 第 2 阶：2 种

    # 从第 3 阶开始递推，每一阶都由前两阶累加而来
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

5. 复杂度

时间复杂度 $O(n)$：从第 3 阶到第 $n$ 阶各计算一次，每次是常数加法。 空间复杂度 $O(n)$：开了一个长度为 $n+1$ 的数组。

6. 空间优化（滚动变量）

观察转移方程 $dp[i] = dp[i-1] + dp[i-2]$，计算 $dp[i]$ 时只用到紧挨着的前两项，更早的值完全用不上了。既然如此，没必要保存整个数组，只用两个变量“滚动前进”即可。这就是著名的滚动变量技巧：用 $O(1)$ 空间代替 $O(n)$ 数组。

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

def climbStairs(n: int) -> int:
    if n <= 2:
        return n

    prev2 = 1  # 相当于 dp[i-2]，初始为 dp[1]
    prev1 = 2  # 相当于 dp[i-1]，初始为 dp[2]

    for _ in range(3, n + 1):
        cur = prev1 + prev2   # 当前阶 = 前一阶 + 前两阶
        prev2 = prev1         # 整体向前滚动一格
        prev1 = cur
    return prev1

优化后空间复杂度降为 $O(1)$，时间不变。“只依赖前几项”是一维 DP 能做滚动优化的信号，请记牢这个判断标准。

二、打家劫舍（198, House Robber / 打家劫舍）

题目：你是一个专业的小偷，沿街有一排房屋，第 $i$ 间藏有金额 $nums[i]$。约束是：相邻的两间房不能在同一晚被盗（否则触发警报）。问在不触警的前提下，今晚最多能偷到多少钱。

1. 状态定义

和爬楼梯不同，这道题要的是“最大值”而不是“方法数”，但一维 DP 的套路完全一致：让状态值就是我们要最大化的目标。

设 $dp[i]$ 表示“只考虑前 $i+1$ 间房子（即下标 $0$ 到 $i$），在合法前提下能偷到的最大金额”。

注意一个容易踩的坑：$dp[i]$ 的含义是“考虑到第 $i$ 间为止的最优解”，而不是“必须偷第 $i$ 间”。这个区别非常重要，它决定了转移方程的形态。我们追求的最终答案是 $dp[n-1]$（考虑完所有房子）。

2. 转移方程

继续用“只盯最后一步”的视角：对于第 $i$ 间房子，我只有两个选择，偷或不偷。

（1）不偷第 $i$ 间：那么收益就等于“考虑到第 $i-1$ 间为止的最优解”，即 $dp[i-1]$。因为没动第 $i$ 间，约束自动满足。

（2）偷第 $i$ 间：拿到 $nums[i]$。但相邻约束要求第 $i-1$ 间必须空着，所以前面只能从第 $i-2$ 间为止的最优解接上，收益是 $dp[i-2] + nums[i]$。

我们要的是最大值，所以两者取较大：

\[dp[i] = \max(dp[i-1],\ dp[i-2] + nums[i])\]

请细品这里的逻辑链：偷第 $i$ 间时为什么是 $dp[i-2]$ 而不是 $dp[i-3]$ 或别的？因为唯一被禁止的是“紧邻的第 $i-1$ 间”，第 $i-2$ 及更早的房子怎么偷都不违反对第 $i$ 间的约束，而 $dp[i-2]$ 已经把“第 $i-2$ 间为止怎么偷最优”算好了。这种“约束只锁住相邻一格、于是跳过一格去取最优子结构”的思路，是这类题的灵魂。

3. 初始化

递推需要 $dp[i-1]$ 和 $dp[i-2]$，所以要确定最前面两项：

$dp[0] = nums[0]$：只有一间房，闭着眼睛偷它就好。 $dp[1] = \max(nums[0],\ nums[1])$：两间相邻，只能二选一，当然挑金额大的那间。

4. Python 代码

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

from typing import List

def rob(nums: List[int]) -> int:
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]

    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, n):
        # 偷第 i 间(dp[i-2]+nums[i]) 与 不偷第 i 间(dp[i-1]) 取较大者
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[n - 1]

5. 复杂度

时间复杂度 $O(n)$：从下标 2 到 $n-1$ 各做一次常数运算。 空间复杂度 $O(n)$：一个长度为 $n$ 的数组。

6. 空间优化（滚动变量）

又是熟悉的味道：$dp[i]$ 只依赖 $dp[i-1]$ 与 $dp[i-2]$，于是同样可以滚动。

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

from typing import List

def rob(nums: List[int]) -> int:
    prev2 = 0  # dp[i-2]，从"还没开始偷"的 0 起步
    prev1 = 0  # dp[i-1]

    for x in nums:
        # cur 即 dp[i]：不偷(prev1) vs 偷(prev2 + x)
        cur = max(prev1, prev2 + x)
        prev2 = prev1  # 向前滚动
        prev1 = cur
    return prev1

这版写法尤其优雅：把 $prev2$、$prev1$ 都初始化为 0，自然涵盖了空数组、单间房等边界，不用单独写 if 判断。空间降到 $O(1)$。建议你对照着把 $nums=[2,7,9,3,1]$ 手动跑一遍 $prev$ 的变化，会对“滚动”有非常实感的理解。

三、最大子数组和（53, Maximum Subarray / 最大子数组和，即 Kadane 算法）

题目：给定一个整数数组 $nums$，找出一个具有最大和的连续子数组（子数组至少包含一个元素），返回这个最大和。

1. 状态定义

这道题的状态定义有个经典的“坑”，正好用来训练定义状态的敏感度。

一个很自然但错误的想法是：设 $dp[i]$ = “前 $i+1$ 个元素中，最大子数组和”。看起来合理，但你会发现根本写不出转移方程。为什么？因为“前 $i$ 个的最优子数组”可能压根不挨着第 $i$ 个元素，那当我新增第 $i$ 个元素时，无法判断它能不能接到那段最优子数组后面。子结构断了，递推就断了。

正确的定义要带上一个关键约束，强制子数组以第 $i$ 个元素结尾：

设 $dp[i]$ 表示“在所有以 $nums[i]$ 为结尾的连续子数组中，最大的那个和”。

加上“必须以 $i$ 结尾”这个约束后，相邻状态立刻有了清晰的承接关系（下面会看到）。代价是：$dp[i]$ 不再直接是最终答案，因为最优子数组可能以任意位置结尾。所以最终答案是 $\max(dp[0], dp[1], \dots, dp[n-1])$，需要在递推过程中顺手记录全局最大值。

这个“为了让子结构成立，主动给状态加一条结尾/起点约束”的手法，是 DP 设计中极其重要的一招，务必体会。

2. 转移方程

考虑“以 $nums[i]$ 结尾”的最大子数组，它的最后一个元素必然是 $nums[i]$。那么它的倒数第二段是什么？只有两种可能：

（1）这个子数组就只有 $nums[i]$ 自己（前面不接任何东西），和为 $nums[i]$； （2）它由“以 $nums[i-1]$ 结尾的某个子数组”再接上 $nums[i]$ 而成，和为 $dp[i-1] + nums[i]$。

要让和最大，在两者中取较大：

\[dp[i] = \max(nums[i],\ dp[i-1] + nums[i])\]

可以提取出一个更直观的等价写法：$dp[i] = \max(dp[i-1], 0) + nums[i]$。意思是，前面那段累积和（$dp[i-1]$）如果是正的，就接上去带来增益；如果是负的，干脆抛弃前缀、从 $nums[i]$ 重新开始。这正是 Kadane 算法的精髓：一旦累积和变成负担（小于 0），立即丢弃重启。

3. 初始化

子数组至少含一个元素，且必须以第 0 个元素结尾，所以最朴素的起点是：

$dp[0] = nums[0]$。

同时设全局答案 $ans = nums[0]$（不能初始化成 0，否则数组全为负数时会得出错误的 0）。

4. Python 代码

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

from typing import List

def maxSubArray(nums: List[int]) -> int:
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]      # 以第 0 个元素结尾，只能是它自己
    ans = nums[0]        # 全局最大值，初值取首元素而非 0

    for i in range(1, n):
        # 要么把前缀(dp[i-1])接上 nums[i]，要么从 nums[i] 重新开始
        dp[i] = max(nums[i], dp[i - 1] + nums[i])
        ans = max(ans, dp[i])   # 实时更新全局最大

    return ans

5. 复杂度

时间复杂度 $O(n)$：单趟扫描。 空间复杂度 $O(n)$：dp 数组。这已经把暴力枚举所有子数组的 $O(n^2)$（甚至 $O(n^3)$）大幅压缩了。

6. 空间优化（滚动变量）

$dp[i]$ 只用到 $dp[i-1]$ 一项，所以连两个变量都不用，一个滚动变量就够了。优化后的版本就是教科书上的 Kadane 算法：

1
2
3
4
5
6
7
8
9
10

from typing import List

def maxSubArray(nums: List[int]) -> int:
    cur = nums[0]   # 以当前元素结尾的最大子数组和(相当于 dp[i])
    ans = nums[0]   # 全局最大子数组和

    for x in nums[1:]:
        cur = max(x, cur + x)   # 接上前缀，或从 x 重新开始
        ans = max(ans, cur)     # 更新全局答案
    return ans

短短几行，时间 $O(n)$、空间 $O(1)$。请记住 Kadane 的一句话总结：“只要前面累积和为负就清零重来，并随时记录见过的最大值。” 这道题是面试高频题，建议背到能默写。

四、零钱兑换（322, Coin Change / 零钱兑换）

题目：给定不同面额的硬币 $coins$ 和一个总金额 $amount$。计算凑成该总金额所需的最少硬币个数。每种硬币数量无限。如果没有任何组合能凑出该金额，返回 $-1$。

1. 状态定义

前三题的“自由变量”都是“数组下标 $i$”，这道题换了一个味道，自由变量是“金额”。这正好说明：一维 DP 的那一维，不一定是数组下标，凡是能描述子问题规模的单一量都可以。

设 $dp[a]$ 表示“凑出金额 $a$ 所需的最少硬币数”。

子问题的规模就是金额 $a$，从 0 一路推到 $amount$，最终答案是 $dp[amount]$。把“金额”当状态的好处是：大金额一定能拆成“小金额 + 一枚硬币”，子问题天然嵌套，递推关系顺理成章。

2. 转移方程

老规矩，盯住“最后一步”：要凑出金额 $a$，我最后放下的那一枚硬币面额是多少？假设它是 $coins$ 里的某个 $c$（前提 $c \le a$）。放下这枚 $c$ 之前，我必须已经用最少的硬币凑好了金额 $a - c$，也就是 $dp[a-c]$ 枚。再加上当前这一枚，总数是 $dp[a-c] + 1$。

但最后这枚硬币可以是任意一种面额，我们要在所有可行的 $c$ 中取最少的方案：

\[dp[a] = \min_{c \in coins,\ c \le a}\big(dp[a-c] + 1\big)\]

如果对某个 $a$，所有面额都凑不出（即没有任何 $dp[a-c]$ 是可达的），那 $dp[a]$ 保持“不可达”状态。

这里和前面“两选一”的题不同：转移不再是固定的两项相加/取大，而是对每一种硬币都试一遍、取最优。所以代码里会出现“内层遍历所有硬币”的循环。这是 DP 从“线性递推”走向“枚举决策 + 取最优”的一个重要升级，请重点感受。

3. 初始化

$dp[0] = 0$：凑出金额 0 不需要任何硬币，这是递推的根基，也是所有正确组合最终回溯到的终点。

其余 $dp[a]$（$a \ge 1$）初始化为一个“不可达”的哨兵值。常用 $amount + 1$（因为凑出 $amount$ 最多也就用 $amount$ 枚面额为 1 的硬币，所以 $amount+1$ 必然大于任何真实答案，是安全的“正无穷”替身）。最后若 $dp[amount]$ 仍等于这个哨兵值，说明无解，返回 $-1$。

用 $amount+1$ 而不是 Python 的 float('inf')，好处是后面写 dp[a-c] + 1 时仍是整数运算，且不会溢出，也便于最后用一句比较判断有没有解。

4. Python 代码

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

from typing import List

def coinChange(coins: List[int], amount: int) -> int:
    INF = amount + 1                 # 哨兵：表示"暂时不可达"的极大值
    dp = [INF] * (amount + 1)
    dp[0] = 0                        # 凑出金额 0 需要 0 枚硬币

    # 从金额 1 逐个金额往上推
    for a in range(1, amount + 1):
        for c in coins:              # 枚举"最后一枚"硬币的面额
            if c <= a:               # 这枚硬币不能超过当前金额
                dp[a] = min(dp[a], dp[a - c] + 1)

    # 若仍是哨兵值，说明凑不出，返回 -1
    return dp[amount] if dp[amount] != INF else -1

5. 复杂度

时间复杂度 $O(amount \times len(coins))$：外层遍历每个金额（$amount$ 个），内层遍历每种硬币。 空间复杂度 $O(amount)$：一维 dp 数组，长度为 $amount+1$。

6. 空间优化（滚动变量？）

这是本节特意安排的一处“反差”，请认真读。前三道题都能把 $O(n)$ 空间压成 $O(1)$，原因是它们的转移只依赖固定的前一两项。但零钱兑换的转移 $dp[a] = \min_c (dp[a-c] + 1)$ 依赖的是 $dp[a-c]$，而 $c$ 可以是任意面额，于是它可能回看很远（比如面额 50 就要回看 $dp[a-50]$）。既然回看的距离不固定、跨度可能很大，就无法用固定数量的滚动变量替代整个数组。

所以这道题在这种一维 dp 表述下，$O(amount)$ 的空间已经是该写法的下界，不能再降。这恰好给我们一个宝贵的认识：

滚动变量优化不是万能的，它的适用前提是“状态只依赖最近、固定数量的前几个状态”。 一旦转移会回看到不固定、可能很远的位置，dp 数组就必须完整保留。爬楼梯、打家劫舍、最大子数组和满足这个前提，所以能优化；零钱兑换不满足，所以不能。能判断“何时可以滚动、何时不能”，比单纯会写滚动代码更重要。

（顺带一提：零钱兑换其实属于“完全背包”模型，后续讲背包专题时还会再次遇见它，到时你会看到另一种以“硬币种类”为外层循环的写法。）

本节小结

把四道题横向对比，能提炼出一维 DP 的通用方法论：

题目状态定义转移方程核心能否滚动到 $O(1)$
70 爬楼梯$dp[i]$=到第 $i$ 阶的走法数$dp[i]=dp[i-1]+dp[i-2]$能（只看前两项）
198 打家劫舍$dp[i]$=前 $i$ 间的最大金额$dp[i]=\max(dp[i-1],\ dp[i-2]+nums[i])$能（只看前两项）
53 最大子数组和$dp[i]$=以 $i$ 结尾的最大和$dp[i]=\max(nums[i],\ dp[i-1]+nums[i])$能（只看前一项）
322 零钱兑换$dp[a]$=凑出金额 $a$ 的最少硬币数$dp[a]=\min_c(dp[a-c]+1)$不能（回看距离不固定）

请把这几条规律刻进脑子里：

第一，定义状态时优先让“状态值”就是题目要的那个量（方法数、最大金额、最大和、最少硬币数）。

第二，转移方程几乎都从“盯住最后一步有哪几种可能”推出来，把“前面怎么来的”信任地交给子问题去封装。

第三，当线性递推的子结构断裂时，给状态加一条约束（如“以 $i$ 结尾”）往往能救活它，代价是最终答案要在所有状态里取最优。

第四，滚动变量优化有前提：只有“依赖最近、固定数量前驱”的转移才能压到 $O(1)$，回看距离不固定的（如零钱兑换）必须保留完整数组。

吃透这四题，再去看任何一维 DP，你都会有一种“似曾相识”的笃定感。下一节我们会进入二维 DP，自由变量变成两个，但思维的内核，状态定义、盯最后一步、子结构、初始化，完全一脉相承。

经典题精讲（二）：二维与序列 DP

上一节我们把一维 DP 的几道经典题吃透了。这一节我们升级难度，进入二维 DP 与序列 DP 的世界。所谓二维，指的是状态需要两个下标 $i, j$ 才能描述清楚，对应的 DP 表是一张二维网格；填表的顺序、转移依赖的方向，都比一维要讲究。

我会延续上一节的固定结构，每道题都按这五步走：

  1. 题意与直觉：先把题读懂，建立朴素的感性认识。
  2. 状态定义：明确 $dp$ 数组的每一维代表什么，$dp[i][j]$ 到底装的是什么含义。这是最关键、最容易翻车的一步。
  3. 转移方程：从状态定义推导出递推关系，并解释为什么是这样。
  4. 初始化与边界、填表顺序：DP 表的第一行第一列怎么填，整张表按什么顺序一格一格填满。
  5. Python 代码与空间优化：先写清晰的二维版本，再压缩成一维（如果可以）。

本节涵盖的题目：

  • 不同路径（62, Unique Paths），最干净的网格 DP 入门。
  • 最长公共子序列（1143, Longest Common Subsequence），序列对齐类问题的母题。
  • 编辑距离（72, Edit Distance），LCS 的近亲，工业界高频。
  • 最长递增子序列（300, Longest Increasing Subsequence），给出 $O(n^2)$ 和 $O(n\log n)$ 两种解法。
  • 0/1 背包 与 其应用 分割等和子集（416, Partition Equal Subset Sum），背包模型的开山。

读完这一节，你应该能看着一道新题，自己判断它属于哪一类、状态该怎么开、表该怎么填。

一、不同路径（62, Unique Paths）

题意与直觉

一个 $m \times n$ 的网格，机器人从左上角（标记为 Start）出发，每次只能向右或向下走一步，问走到右下角（标记为 Finish）一共有多少条不同的路径。

举个最小的例子：$2 \times 2$ 的网格。从左上到右下，要么「先右后下」，要么「先下后右」，一共 $2$ 条。再大一点 $3 \times 3$，画一画会发现是 $6$ 条。规律不那么直观，但用 DP 一推就清楚了。

直觉是这样的：要到达某一格，机器人上一步只可能从它的左边一格过来，或者从它的上边一格过来（因为只能向右或向下）。所以「到达这一格的路径数」就等于「到达左边那格的路径数」加上「到达上边那格的路径数」。这就是一个天然的递推。

状态定义

设 $dp[i][j]$ 表示：从起点 $(0,0)$ 走到格子 $(i, j)$ 的不同路径总数。

这里 $i$ 是行下标（从上到下，$0$ 到 $m-1$），$j$ 是列下标（从左到右，$0$ 到 $n-1$）。我们最终要的答案是 $dp[m-1][n-1]$。

转移方程

对于不在第一行也不在第一列的内部格子：

\[dp[i][j] = dp[i-1][j] + dp[i][j-1]\]

含义：到 $(i,j)$ 的路径，最后一步要么从上方 $(i-1, j)$ 下来，要么从左方 $(i, j-1)$ 过来，两类互不重叠，直接相加。

初始化与边界、填表顺序

边界要特别小心。第一行的格子 $(0, j)$，机器人只能一路向右才能到，路径只有一条；同理第一列的格子 $(i, 0)$ 也只有一条（一路向下）。所以：

\[dp[0][j] = 1 \quad（所有 j），\qquad dp[i][0] = 1 \quad（所有 i）\]

填表顺序：从上到下、从左到右逐行扫描。这样在计算 $dp[i][j]$ 时，它依赖的 $dp[i-1][j]$（正上方，上一行已算完）和 $dp[i][j-1]$（正左方，本行左边已算完）一定都是已知的。

用文字一格一格填这张表（以 $m=3, n=3$ 为例）

先把第一行和第一列全填 $1$：

1
2
3

1  1  1
1  ?  ?
1  ?  ?

现在填 $(1,1)$：它等于上方 $(0,1)=1$ 加左方 $(1,0)=1$，得 $2$。 再填 $(1,2)$：上方 $(0,2)=1$ 加左方 $(1,1)=2$，得 $3$。

1
2
3

1  1  1
1  2  3
1  ?  ?

填 $(2,1)$：上方 $(1,1)=2$ 加左方 $(2,0)=1$，得 $3$。 填 $(2,2)$：上方 $(1,2)=3$ 加左方 $(2,1)=3$，得 $6$。

1
2
3

1  1  1
1  2  3
1  3  6

右下角是 $6$，正是答案。你能清楚看到：每个内部格子的值，都是它正上方和正左方两个数之和，像帕斯卡三角形一样从左上角往右下角「长」出来。

Python 代码（二维版本）

1
2
3
4
5
6
7
8
9
10
11

def uniquePaths(m: int, n: int) -> int:
    # dp[i][j]: 从 (0,0) 到 (i,j) 的不同路径数
    dp = [[1] * n for _ in range(m)]  # 第一行、第一列天然全是 1

    # 从 (1,1) 开始逐行逐列填表
    for i in range(1, m):
        for j in range(1, n):
            # 只能从上方或左方走来，两类路径相加
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[m - 1][n - 1]

空间优化（压成一维）

注意到 $dp[i][j]$ 只用到上一行（$dp[i-1][\cdot]$）和当前行已算好的左边一格（$dp[i][j-1]$）。我们可以只保留一行，用滚动数组覆盖更新。关键技巧：当我们就地更新 dp[j] 时，更新前的 dp[j] 恰好是「上一行的值」（即 $dp[i-1][j]$），而 dp[j-1] 是「当前行左边刚算好的值」（即 $dp[i][j-1]$）。两者正好凑齐转移所需。

1
2
3
4
5
6
7
8
9
10

def uniquePaths(m: int, n: int) -> int:
    # 只保留一行，初始为全 1（代表第一行）
    dp = [1] * n

    for _ in range(1, m):           # 逐行向下推进
        for j in range(1, n):       # 行内从左到右
            # 更新前 dp[j] = 上一行值，dp[j-1] = 当前行左邻值
            dp[j] += dp[j - 1]

    return dp[-1]

空间从 $O(mn)$ 降到 $O(n)$，时间仍是 $O(mn)$。dp[j] += dp[j-1] 这一行就是 dp[j] = dp[j]（上方） + dp[j-1]（左方） 的紧凑写法，体会一下滚动数组的精髓。

二、最长公共子序列（1143, Longest Common Subsequence）

题意与直觉

给两个字符串 text1 和 text2，求它们最长公共子序列的长度。子序列（subsequence）是指：从原串中删掉若干（可以是零个）字符后，剩下字符保持原相对顺序得到的串，不要求连续。

例如 text1 = "abcde"，text2 = "ace"，公共子序列有 "ace"，长度 $3$，这就是最长的。

这是序列对齐类问题的母题，理解了它，编辑距离、最短编辑、最小删除等一大批题都迎刃而解。直觉的核心：比较两个串，我们从末尾字符开始考虑。如果两个串的最后一个字符相同，那它一定可以放进公共子序列里（贪心地用上它绝不亏）；如果不同，那这两个末尾字符至少有一个用不上，我们分别丢掉一个再比较，取较优者。这个「比较末尾、相同则配对、不同则各退一步」的思路，是所有双序列 DP 的灵魂。

状态定义

设 $dp[i][j]$ 表示：text1 的前 $i$ 个字符（即 text1[0:i]）与 text2 的前 $j$ 个字符（即 text2[0:j]）的最长公共子序列长度。

特别注意：这里用「前 $i$ 个字符」而不是「以第 $i$ 个字符结尾」。$i$ 的取值范围是 $0$ 到 $m$（$m$ 是 text1 长度），$i=0$ 表示空串。这种「前缀长度」定义法会让边界处理变得异常干净，是双序列 DP 的标准套路，请务必记牢。答案是 $dp[m][n]$。

转移方程

设 text1 长度为 $m$，text2 长度为 $n$。对 $1 \le i \le m$、$1 \le j \le n$：

  • 当 text1[i-1] == text2[j-1]（两个前缀的最后一个字符相同，注意下标错位）：
\[dp[i][j] = dp[i-1][j-1] + 1\]

含义：这对相同字符配对，贡献 $1$ 的长度，剩下的问题缩小为「text1 前 $i-1$ 个」与「text2 前 $j-1$ 个」。

  • 当 text1[i-1] != text2[j-1]（最后字符不同）：
\[dp[i][j] = \max\big(dp[i-1][j],\ dp[i][j-1]\big)\]

含义：末尾两字符不能同时用上，要么放弃 text1 的第 $i$ 个字符（看 $dp[i-1][j]$），要么放弃 text2 的第 $j$ 个字符（看 $dp[i][j-1]$），取两者较大的。

初始化与边界、填表顺序

边界非常优雅：只要有一个串是空串，公共子序列长度必为 $0$。所以：

\[dp[0][j] = 0 \quad（所有 j），\qquad dp[i][0] = 0 \quad（所有 i）\]

这就是为什么我们多开一行一列（尺寸 $(m+1) \times (n+1)$）、并用「前缀长度」定义的好处：第 $0$ 行第 $0$ 列天然代表空串，不需要任何特殊判断。

填表顺序：从上到下、从左到右。计算 $dp[i][j]$ 时依赖左上方 $dp[i-1][j-1]$、正上方 $dp[i-1][j]$、正左方 $dp[i][j-1]$，这三个在逐行逐列扫描下都已算好。

用文字一格一格填这张表（text1 = "abcde"，text2 = "ace"）

表是 $6 \times 4$（行对应 text1 的前缀长度 $0..5$，列对应 text2 的前缀长度 $0..3$）。第 $0$ 行、第 $0$ 列全是 $0$。我把行标注成对应字符以便阅读：

1
2
3
4
5
6
7

        ""   a    c    e      <- text2 前缀
   ""    0   0    0    0
   a     0   ?    ?    ?
   b     0
   c     0
   d     0
   e     0

填 $(1,1)$：text1[0]='a' 与 text2[0]='a' 相同，取左上 $dp[0][0]=0$ 加 $1$，得 $1$。 填 $(1,2)$：'a' 与 'c' 不同，取 $\max(dp[0][2], dp[1][1]) = \max(0, 1) = 1$。 填 $(1,3)$：'a' 与 'e' 不同，取 $\max(dp[0][3], dp[1][2]) = \max(0,1) = 1$。

第 a 行算完：0 1 1 1。

第 b 行：'b' 和 a/c/e 都不同，每格都取上方与左方的较大者，结果维持 0 1 1 1（因为 b 没带来任何新的公共字符）。

第 c 行：

  • $(3,1)$：'c' vs 'a' 不同，$\max(dp[2][1]=1, dp[3][0]=0)=1$。
  • $(3,2)$：'c' vs 'c' 相同！取左上 $dp[2][1]=1$ 加 $1$，得 $2$。
  • $(3,3)$：'c' vs 'e' 不同，$\max(dp[2][3]=1, dp[3][2]=2)=2$。

第 c 行：0 1 2 2。

第 d 行：'d' 和谁都不同，照搬上方/左方较大者，得 0 1 2 2。

第 e 行：

  • $(5,1)$：'e' vs 'a' 不同，$\max(1,0)=1$。
  • $(5,2)$：'e' vs 'c' 不同，$\max(dp[4][2]=2, dp[5][1]=1)=2$。
  • $(5,3)$：'e' vs 'e' 相同！取左上 $dp[4][2]=2$ 加 $1$，得 $3$。

完整的表：

1
2
3
4
5
6
7

        ""   a    c    e
   ""    0   0    0    0
   a     0   1    1    1
   b     0   1    1    1
   c     0   1    2    2
   d     0   1    2    2
   e     0   1    2    3

右下角 $dp[5][3] = 3$，正是 "ace" 的长度。观察填表过程：相同字符时数值沿对角线「跳一级加一」，不同字符时数值从上方或左方「平移过来」，整张表的数值单调不减地往右下角累积。

Python 代码（二维版本）

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

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    # dp[i][j]: text1 前 i 个字符 与 text2 前 j 个字符 的 LCS 长度
    # 多开一行一列代表空串，初值全 0（边界天然成立）
    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]:
                # 末尾字符配对，长度 +1，子问题缩到 (i-1, 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]

空间优化（压成一维）

$dp[i][j]$ 依赖正上方 $dp[i-1][j]$、正左方 $dp[i][j-1]$、左上方 $dp[i-1][j-1]$。压成一行时，正左方就在当前行已算好的位置，正上方是「更新前的 dp[j]」，但左上方 $dp[i-1][j-1]$ 会在我们更新 dp[j-1] 时被冲掉。所以需要一个临时变量 prev 把它提前保存下来。

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

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [0] * (n + 1)  # 仅保留一行，初始代表 i=0（空串）

    for i in range(1, m + 1):
        prev = 0  # prev 保存 dp[i-1][j-1]（左上角），行首对应 j=0，值为 0
        for j in range(1, n + 1):
            temp = dp[j]  # 更新前的 dp[j] 就是 dp[i-1][j]（正上方），先存好
            if text1[i - 1] == text2[j - 1]:
                dp[j] = prev + 1            # prev = dp[i-1][j-1]（左上方）
            else:
                dp[j] = max(dp[j], dp[j - 1])  # dp[j]=上方, dp[j-1]=左方
            prev = temp  # 进入下一列前，本格的「旧上方」成为下格的「左上方」
        # 行末无需特殊处理
    return dp[n]

空间从 $O(mn)$ 降到 $O(n)$。这个 prev 暂存左上角的技巧，是双序列 DP 一维压缩的通用手法，编辑距离里我们还会用到它。

三、编辑距离（72, Edit Distance）

题意与直觉

给两个单词 word1 和 word2，求把 word1 转换成 word2 所需的最少操作数。允许三种操作，每次作用于一个字符：插入一个字符、删除一个字符、替换一个字符。

例如 word1 = "horse"，word2 = "ros"，最少 $3$ 步：horse -> rorse（把 h 替换成 r）-> rose（删 r）-> ros（删 e）。

它和 LCS 是近亲：同样是双序列、同样从末尾字符切入。直觉是：要把 word1 的前缀变成 word2 的前缀，看两者末尾字符。如果末尾相同，这个字符不用动，问题直接缩小；如果不同，我们有三种「补救」方式（替换、删除、插入），各对应一种子问题，取代价最小的那条路。这是工业界（拼写纠错、DNA 比对、diff 工具）的高频基础算法。

状态定义

设 $dp[i][j]$ 表示：把 word1 的前 $i$ 个字符转换成 word2 的前 $j$ 个字符所需的最少操作数。

同样采用「前缀长度」定义，$i \in [0, m]$，$j \in [0, n]$。答案是 $dp[m][n]$。

转移方程

设 word1 长 $m$、word2 长 $n$。对 $1 \le i \le m$、$1 \le j \le n$：

  • 当 word1[i-1] == word2[j-1]（末尾字符相同，无需操作）：
\[dp[i][j] = dp[i-1][j-1]\]
  • 当 word1[i-1] != word2[j-1]（末尾不同，三选一）：
\[dp[i][j] = 1 + \min\big(dp[i-1][j-1],\ dp[i-1][j],\ dp[i][j-1]\big)\]

这三项分别对应三种操作，请逐一理解（这是本题最难的一步）：

  • $dp[i-1][j-1]$ ：替换。把 word1 的第 $i$ 个字符替换成 word2 的第 $j$ 个字符，配对后两边都缩一位。
  • $dp[i-1][j]$ ：删除。删掉 word1 的第 $i$ 个字符，问题变成「word1 前 $i-1$ 个 -> word2 前 $j$ 个」。
  • $dp[i][j-1]$ ：插入。在 word1 末尾插入一个等于 word2[j-1] 的字符（把 word2 的第 $j$ 个字符补上），问题变成「word1 前 $i$ 个 -> word2 前 $j-1$ 个」。

无论哪种操作都消耗 $1$ 步，所以外面统一加 $1$，再在三者中取最小。

初始化与边界、填表顺序

边界这次不是全 $0$，要想清楚：

  • $dp[i][0]$ ：把 word1 前 $i$ 个字符变成空串，只能逐个删除，需要 $i$ 步。所以 $dp[i][0] = i$。
  • $dp[0][j]$ ：把空串变成 word2 前 $j$ 个字符，只能逐个插入，需要 $j$ 步。所以 $dp[0][j] = j$。
  • 角落 $dp[0][0] = 0$（空串到空串，零操作）。

填表顺序仍是从上到下、从左到右；$dp[i][j]$ 依赖的左上、正上、正左三格在此顺序下都已就绪。

用文字一格一格填这张表（word1 = "horse"，word2 = "ros"）

表是 $6 \times 4$。先填边界：第 $0$ 行是 0 1 2 3（空串变 r/ro/ros），第 $0$ 列是 0 1 2 3 4 5（horse 各前缀删空）。

1
2
3
4
5
6
7

        ""   r    o    s
   ""    0   1    2    3
   h     1   ?    ?    ?
   o     2   ?    ?    ?
   r     3   ?    ?    ?
   s     4   ?    ?    ?
   e     5   ?    ?    ?

第 h 行（word1[0]='h'）：

  • $(1,1)$：'h' vs 'r' 不同，$1 + \min(dp[0][0]=0,\ dp[0][1]=1,\ dp[1][0]=1) = 1+0 = 1$。
  • $(1,2)$：'h' vs 'o' 不同，$1 + \min(dp[0][1]=1,\ dp[0][2]=2,\ dp[1][1]=1) = 1+1 = 2$。
  • $(1,3)$：'h' vs 's' 不同，$1 + \min(dp[0][2]=2,\ dp[0][3]=3,\ dp[1][2]=2) = 1+2 = 3$。

第 h 行：1 1 2 3。

第 o 行（'o'）：

  • $(2,1)$：'o' vs 'r' 不同，$1 + \min(dp[1][0]=1, dp[1][1]=1, dp[2][0]=2) = 1+1 = 2$。
  • $(2,2)$：'o' vs 'o' 相同！$dp[2][2] = dp[1][1] = 1$。
  • $(2,3)$：'o' vs 's' 不同，$1 + \min(dp[1][2]=2, dp[1][3]=3, dp[2][2]=1) = 1+1 = 2$。

第 o 行：2 2 1 2。

第 r 行（'r'）：

  • $(3,1)$：'r' vs 'r' 相同！$dp[3][1] = dp[2][0] = 2$。
  • $(3,2)$：'r' vs 'o' 不同，$1 + \min(dp[2][1]=2, dp[2][2]=1, dp[3][1]=2) = 1+1 = 2$。
  • $(3,3)$：'r' vs 's' 不同，$1 + \min(dp[2][2]=1, dp[2][3]=2, dp[3][2]=2) = 1+1 = 2$。

第 r 行：3 2 2 2。

第 s 行（'s'）：

  • $(4,1)$：'s' vs 'r' 不同，$1 + \min(dp[3][0]=3, dp[3][1]=2, dp[4][0]=4) = 1+2 = 3$。
  • $(4,2)$：'s' vs 'o' 不同，$1 + \min(dp[3][1]=2, dp[3][2]=2, dp[4][1]=3) = 1+2 = 3$。
  • $(4,3)$：'s' vs 's' 相同！$dp[4][3] = dp[3][2] = 2$。

第 s 行：4 3 3 2。

第 e 行（'e'）：

  • $(5,1)$：'e' vs 'r' 不同，$1 + \min(dp[4][0]=4, dp[4][1]=3, dp[5][0]=5) = 1+3 = 4$。
  • $(5,2)$：'e' vs 'o' 不同，$1 + \min(dp[4][1]=3, dp[4][2]=3, dp[5][1]=4) = 1+3 = 4$。
  • $(5,3)$：'e' vs 's' 不同，$1 + \min(dp[4][2]=3, dp[4][3]=2, dp[5][2]=4) = 1+2 = 3$。

完整的表：

1
2
3
4
5
6
7

        ""   r    o    s
   ""    0   1    2    3
   h     1   1    2    3
   o     2   2    1    2
   r     3   2    2    2
   s     4   3    3    2
   e     5   4    4    3

右下角 $dp[5][3] = 3$，正是答案。留意对角线上那串相同字符（o、r、s）带来的「免费继承」$dp[i-1][j-1]$，它们把代价压低；不同字符处则在三个邻居里挑最便宜的一条路加一。

Python 代码（二维版本）

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

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    # dp[i][j]: word1 前 i 个 转成 word2 前 j 个 的最少操作数
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 边界：一个串为空时，只能纯插入或纯删除
    for i in range(m + 1):
        dp[i][0] = i  # word1 前 i 个全删光
    for j in range(n + 1):
        dp[0][j] = 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 - 1],  # 替换
                    dp[i - 1][j],      # 删除 word1 末字符
                    dp[i][j - 1],      # 插入 word2 末字符
                )
    return dp[m][n]

空间优化（压成一维）

和 LCS 一样，转移依赖左上、正上、正左三格，压成一行时用 prev 暂存左上角。唯一区别是这里的第 $0$ 列边界不是 $0$ 而是 $i$，所以每行开头要重置 dp[0] = i。

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

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = list(range(n + 1))  # 第 0 行：dp[j] = j（空串变 word2 前 j 个）

    for i in range(1, m + 1):
        prev = dp[0]  # prev = dp[i-1][0] = i-1（左上角的初始值）
        dp[0] = i     # 当前行第 0 列边界：word1 前 i 个删空，需 i 步
        for j in range(1, n + 1):
            temp = dp[j]  # 暂存「正上方」dp[i-1][j]
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev               # 左上方，免操作继承
            else:
                dp[j] = 1 + min(prev, dp[j], dp[j - 1])
                #            左上    上方   左方
            prev = temp  # 本格旧上方 -> 下格左上方
    return dp[n]

时间 $O(mn)$，空间从 $O(mn)$ 降到 $O(n)$。

四、最长递增子序列（300, Longest Increasing Subsequence）

这道题特殊在：它有两种经典解法，$O(n^2)$ 的标准 DP 好理解，$O(n\log n)$ 的二分解法更快但更巧妙。我们都讲透。

题意与直觉

给一个整数数组 nums，求最长严格递增子序列的长度。子序列同样允许删字符、保相对顺序、不要求连续。

例如 nums = [10, 9, 2, 5, 3, 7, 101, 18]，一个最长递增子序列是 [2, 3, 7, 18] 或 [2, 3, 7, 101]，长度 $4$。

解法一：$O(n^2)$ 标准 DP

状态定义

设 $dp[i]$ 表示：以 nums[i] 作为结尾的最长递增子序列的长度。

请注意这里和 LCS 不同，用的是「以第 $i$ 个元素结尾」的定义。为什么？因为递增与否取决于「子序列最后一个元素是谁」，把结尾钉死才能正确判断能不能接上新元素。最终答案不是 $dp[n-1]$，而是 $\max_i dp[i]$（最长子序列可能在任意位置结尾）。

转移方程

对每个 $i$，回头看它前面所有的 $j < i$：如果 nums[j] < nums[i]，说明 nums[i] 可以接在以 nums[j] 结尾的递增子序列后面，长度变成 $dp[j]+1$。在所有可行的 $j$ 里取最大：

\[dp[i] = \max\Big(1,\ \max_{0 \le j < i,\ nums[j] < nums[i]} \big(dp[j] + 1\big)\Big)\]

那个「$1$」是兜底：哪怕前面没有任何元素比它小，nums[i] 自己也能构成长度为 $1$ 的子序列。

初始化与填表顺序

每个 $dp[i]$ 初始化为 $1$（自己单独成序列）。从左到右计算 $dp[0], dp[1], \ldots, dp[n-1]$，计算 $dp[i]$ 时所有 $dp[j]$（$j<i$）都已算好。

用文字一格一格填这张表（nums = [10, 9, 2, 5, 3, 7, 101, 18]）

逐个推：

  • dp[0]（10）：前面没东西，$=1$。
  • dp[1]（9）：前面只有 10，$10 < 9$ 不成立，$=1$。
  • dp[2]（2）：前面 10、9 都不小于 2，$=1$。
  • dp[3]（5）：前面比 5 小的有 2（dp[2]=1），$=1+1=2$。
  • dp[4]（3）：前面比 3 小的有 2（dp[2]=1），$=1+1=2$。
  • dp[5]（7）：前面比 7 小的有 2、5、3，对应 $dp$ 是 $1, 2, 2$，取最大 $2$ 再加 $1$，$=3$。
  • dp[6]（101）：前面所有元素都比 101 小，最大 $dp$ 是 dp[5]=3，$=3+1=4$。
  • dp[7]（18）：前面比 18 小的有 10,9,2,5,3,7，对应 $dp$ 最大是 dp[5]=3，$=3+1=4$。
1
2
3

index:   0    1   2   3   4   5    6    7
nums:    10   9   2   5   3   7    101  18
dp:      1    1   1   2   2   3    4    4

最大值是 $4$，就是答案。可以看到 dp[6]=4 对应 [2,5,7,101] 或 [2,3,7,101]，dp[7]=4 对应 [2,3,7,18]。

Python 代码

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

def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)
    if n == 0:
        return 0
    # dp[i]: 以 nums[i] 结尾的最长严格递增子序列长度
    dp = [1] * n

    for i in range(n):
        for j in range(i):  # 回看所有前驱
            if nums[j] < nums[i]:           # 能接在 nums[j] 之后
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)  # 答案在任意位置结尾，取全局最大

时间 $O(n^2)$，空间 $O(n)$。这里没有进一步的空间优化（$dp$ 本身就是一维），优化的方向是降时间复杂度，见解法二。

解法二：$O(n\log n)$ 贪心 + 二分

核心思路

我们换一个角度，维护一个数组 tails，其中 tails[k] 表示：所有长度为 $k+1$ 的递增子序列里，结尾元素的最小可能值。

为什么维护「最小结尾」？因为结尾越小，后面越容易接上更大的数，越有利于把子序列拉长。这是一个贪心策略。

关键性质：tails 数组始终严格递增。直觉上，能构成更长递增子序列的最小结尾，一定比更短的最小结尾要大。正因为 tails 有序，我们才能用二分查找来定位，把每步的 $O(n)$ 降到 $O(\log n)$。

算法流程

遍历每个数 x：在 tails 中二分查找第一个 $\ge x$ 的位置 pos（即左边界二分）。

  • 如果 pos 等于当前 tails 长度，说明 x 比所有结尾都大，可以接在最长序列后面，让 LIS 变长，把 x 追加到末尾。
  • 否则，用 x 替换 tails[pos]。因为 x 是一个「长度为 pos+1 的递增子序列」的更小（或相等会被严格替换掉）结尾，更新它以保持「最小结尾」的不变量。

最终 tails 的长度就是 LIS 的长度（注意：tails 本身不一定是某个真实的 LIS，但它的长度一定正确）。

用文字一格一格走一遍（nums = [10, 9, 2, 5, 3, 7, 101, 18]）

tails 初始为空 []。逐个处理：

  • x=10：tails 空，二分位置 $0=$ 长度，追加。tails = [10]。
  • x=9：在 [10] 中找第一个 $\ge 9$ 的位置，是 $0$（10>=9），不等于长度，替换 tails[0]。tails = [9]。
  • x=2：在 [9] 中找第一个 $\ge 2$ 的位置，是 $0$，替换。tails = [2]。
  • x=5：在 [2] 中找第一个 $\ge 5$ 的位置，是 $1=$ 长度，追加。tails = [2, 5]。
  • x=3：在 [2,5] 中找第一个 $\ge 3$ 的位置，是 $1$（5>=3），替换 tails[1]。tails = [2, 3]。
  • x=7：在 [2,3] 中找第一个 $\ge 7$ 的位置，是 $2=$ 长度，追加。tails = [2, 3, 7]。
  • x=101：在 [2,3,7] 中找第一个 $\ge 101$ 的位置，是 $3=$ 长度，追加。tails = [2, 3, 7, 101]。
  • x=18：在 [2,3,7,101] 中找第一个 $\ge 18$ 的位置，是 $3$（101>=18），替换 tails[3]。tails = [2, 3, 7, 18]。

最终 tails = [2, 3, 7, 18]，长度 $4$，与解法一答案一致。注意末尾那次替换（101 换成 18）让 tails 的结尾变小了，但长度没变，这正是「保持最小结尾、不影响长度」的体现。

Python 代码（用标准库 bisect）

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

import bisect

def lengthOfLIS(nums: list[int]) -> int:
    tails = []  # tails[k]: 长度为 k+1 的递增子序列的最小结尾

    for x in nums:
        # 找第一个 >= x 的位置（左边界二分）；严格递增故用 bisect_left
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)   # x 比所有结尾都大，LIS 变长
        else:
            tails[pos] = x    # 用更小的结尾替换，维持最小结尾不变量

    return len(tails)

用 bisect_left 找的是「第一个 $\ge x$ 的位置」，这保证了严格递增（相等元素也会触发替换，不会重复计入）。如果题目要求的是非严格递增（允许相等），改用 bisect_right 即可。时间 $O(n\log n)$，空间 $O(n)$。

两种解法怎么选：面试里先写 $O(n^2)$ 版本，思路清晰、不容易错；如果面试官追问优化，再给出二分版本，展示你对「贪心 + 维护单调结构 + 二分」这一组合拳的掌握。注意二分版本只能求长度，若还需要还原具体的子序列，得额外记录前驱指针，此时 $O(n^2)$ 版本反而更方便。

五、0/1 背包 与 分割等和子集（416, Partition Equal Subset Sum）

最后压轴的是背包模型，它是 DP 里应用最广的一类。我们先把 0/1 背包的标准模型讲清楚，再看它在 LeetCode 416 上的经典变形。

5.1 0/1 背包标准模型

问题描述

有 $N$ 件物品和一个容量为 $W$ 的背包。第 $i$ 件物品重量为 $w_i$、价值为 $v_i$。每件物品只能选一次（选或不选，所以叫 0/1）。问在不超过背包容量的前提下，能装入物品的最大总价值。

直觉：对每件物品做一个二元决策，放进背包，或不放。这构成一棵决策树，朴素枚举是 $2^N$ 指数级。DP 的作用就是把重叠的子问题合并掉。

状态定义

设 $dp[i][c]$ 表示：只考虑前 $i$ 件物品、背包容量为 $c$ 时，能获得的最大总价值。

$i \in [0, N]$，$c \in [0, W]$。答案是 $dp[N][W]$。

转移方程

对第 $i$ 件物品（下标对应 $w_{i-1}, v_{i-1}$，注意错位），考虑两种决策：

  • 不放第 $i$ 件：价值等于只用前 $i-1$ 件、容量仍为 $c$ 的结果，即 $dp[i-1][c]$。
  • 放第 $i$ 件（前提是装得下，$c \ge w_{i-1}$）：先腾出 $w_{i-1}$ 的容量给它，剩下容量 $c - w_{i-1}$ 留给前 $i-1$ 件，再加上它自身价值，即 $dp[i-1][c - w_{i-1}] + v_{i-1}$。

取两者较大：

\[dp[i][c] = \begin{cases} dp[i-1][c], & c < w_{i-1} \\[4pt] \max\big(dp[i-1][c],\ dp[i-1][c - w_{i-1}] + v_{i-1}\big), & c \ge w_{i-1} \end{cases}\]

初始化与填表顺序

边界：$dp[0][c] = 0$（没有物品可选，价值为 $0$）；$dp[i][0] = 0$（容量为 $0$，啥也装不下）。整张表初始化为 $0$ 即可。填表从上到下（物品维）、从左到右（容量维），$dp[i][c]$ 依赖上一行的两格 $dp[i-1][c]$ 与 $dp[i-1][c-w_{i-1}]$，都已就绪。

Python 代码（二维版本）

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

def knapsack_01(weights: list[int], values: list[int], W: int) -> int:
    N = len(weights)
    # dp[i][c]: 前 i 件物品、容量 c 时的最大价值
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i in range(1, N + 1):
        w, v = weights[i - 1], values[i - 1]  # 第 i 件物品的重量与价值
        for c in range(W + 1):
            if c < w:
                dp[i][c] = dp[i - 1][c]            # 装不下，只能不放
            else:
                dp[i][c] = max(
                    dp[i - 1][c],                  # 不放第 i 件
                    dp[i - 1][c - w] + v,          # 放第 i 件
                )
    return dp[N][W]

空间优化（压成一维，背包最经典的技巧）

$dp[i][c]$ 只依赖上一行 $dp[i-1][\cdot]$，于是可以压成一维 dp[c]。但这里有一个极其重要、几乎是背包问题标志性的细节：容量维必须从大到小（逆序）遍历。

为什么逆序？我们要保证「每件物品只用一次」。转移 dp[c] = max(dp[c], dp[c-w] + v) 中，dp[c-w] 必须是上一行（还没考虑第 $i$ 件物品时）的值。如果正序遍历，dp[c-w] 会在本轮被更小的 $c$ 先更新成「已经放过第 $i$ 件物品」的值，导致同一件物品被重复放入（那就变成完全背包了）。逆序遍历时，更大的 $c$ 先算，它引用的 dp[c-w]（更小下标）还停留在上一行的旧值，从而严格保证每件物品至多用一次。

1
2
3
4
5
6
7
8
9
10
11

def knapsack_01(weights: list[int], values: list[int], W: int) -> int:
    N = len(weights)
    dp = [0] * (W + 1)  # dp[c]: 当前已考虑物品下，容量 c 的最大价值

    for i in range(N):
        w, v = weights[i], values[i]
        # 容量逆序遍历，保证每件物品只用一次（核心！）
        for c in range(W, w - 1, -1):  # 从 W 倒着到 w，c<w 的无需更新
            dp[c] = max(dp[c], dp[c - w] + v)

    return dp[W]

请把「0/1 背包 -> 一维 -> 容量逆序」这条链刻进肌肉记忆，它是背包类题目的通用模板。下面的 416 就是它的直接应用。

5.2 分割等和子集（416, Partition Equal Subset Sum）

题意与直觉

给一个只含正整数的数组 nums，判断能否把它分成两个子集，使两个子集的元素和相等。

例如 nums = [1, 5, 11, 5]，可以分成 [1, 5, 5] 和 [11]，两边和都是 $11$，返回 True。而 nums = [1, 2, 3, 5] 无论怎么分都做不到，返回 False。

关键转化（把它变成背包）

两个子集和相等，意味着每个子集的和都是总和的一半。设 total = sum(nums)：

  • 如果 total 是奇数，绝无可能均分，直接返回 False。
  • 否则令 target = total // 2。问题转化为：能否从 nums 中选出若干个数，使它们的和恰好等于 target。

这正是一个 0/1 背包：把每个数字既当「重量」又当「容量消耗」，背包容量是 target，问能否「恰好装满」。每个数字只能用一次（0/1）。这一步转化是本题的全部精髓。

状态定义

设 $dp[c]$（直接用一维讲，因为最实用）表示：能否从已考虑的数字中选出一个子集，使其和恰好等于 $c$。这是个布尔值。

二维写法是 $dp[i][c]$ 表示「前 $i$ 个数能否凑出和 $c$」，但背包压缩后一维更简洁，我们直接讲一维。

转移方程

考虑第 $i$ 个数字 num，对容量 $c$：

\[dp[c] = dp[c] \ \text{or}\ dp[c - num] \quad （当 c \ge num）\]

含义：容量 $c$ 能否凑出，有两种可能，本来不选 num 就能凑出（旧的 dp[c] 为真），或者选上 num、让前面的数凑出 $c - num$（dp[c-num] 为真）。两者或起来。

初始化与填表顺序

边界：$dp[0] = \text{True}$（和为 $0$ 永远可以凑出，一个数都不选）；其余 $dp[c] = \text{False}$。

填表：外层遍历每个数字，内层容量从大到小逆序到 num（和 0/1 背包同样的理由：保证每个数字只用一次）。

用文字一格一格填（nums = [1, 5, 11, 5]，total = 22，target = 11）

dp 长度 $12$（下标 $0..11$），初始 dp[0]=True，其余 False：

1
2

index: 0  1  2  3  4  5  6  7  8  9  10 11
dp:    T  F  F  F  F  F  F  F  F  F  F  F

处理 num=1（c 从 11 逆序到 1）：只有 dp[1] = dp[1] or dp[0] = T。其余 dp[c] or dp[c-1] 因为右侧还是 F 而不变。

1

dp:    T  T  F  F  F  F  F  F  F  F  F  F

处理 num=5（c 从 11 逆序到 5）：

  • dp[6] = dp[6] or dp[1] = T
  • dp[5] = dp[5] or dp[0] = T （其余 dp[c-5] 为 F，不变。逆序保证我们引用的是「还没用过这个 5」时的状态。）
1

dp:    T  T  F  F  F  T  T  F  F  F  F  F

处理 num=11（c 从 11 逆序到 11）：

  • dp[11] = dp[11] or dp[0] = T！已经凑出 $11$。
1

dp:    T  T  F  F  F  T  T  F  F  F  F  T

此时 dp[11] 已为 True，答案就是 True。即使继续处理 num=5（第二个 5），结论不变。注意这里凑出 $11$ 用的是单个数字 $11$，对应另一个子集 [1,5,5]。

Python 代码（一维背包）

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

def canPartition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False  # 奇数和绝不可能均分

    target = total // 2
    # dp[c]: 能否选出子集使其和恰好为 c
    dp = [False] * (target + 1)
    dp[0] = True  # 和为 0 总能凑出（空集）

    for num in nums:
        # 容量逆序，保证每个数字只用一次（0/1 背包标志性写法）
        for c in range(target, num - 1, -1):
            dp[c] = dp[c] or dp[c - num]
            # 小优化：一旦凑出 target 即可提前返回
        if dp[target]:
            return True

    return dp[target]

时间复杂度 $O(N \times target)$，空间 $O(target)$。这道题把抽象的「能否均分」翻译成具体的「能否凑出总和一半」，再套用 0/1 背包模板，是「问题转化 + 经典模型」这一解题范式的绝佳示范。

本节小结

把这一节的几道题横向对比，你会看到二维/序列 DP 的几条主线：

题目（题号）状态定义关键转移核心空间优化
不同路径（62）$dp[i][j]$ 到 $(i,j)$ 的路径数上 + 左滚动一行，正序
最长公共子序列（1143）前 $i$、前 $j$ 的 LCS相同则对角加一，否则取上/左较大一行 + prev 存左上
编辑距离（72）前 $i$ 变前 $j$ 的最少操作相同则继承左上，否则三邻居取 min 加一一行 + prev 存左上
最长递增子序列（300）以 $i$ 结尾的 LIS 长度 / tails 最小结尾回看前驱取 max+1 / 二分替换本就一维 / 二分降时间
分割等和子集（416）能否凑出容量 $c$0/1 背包 or 转移一维，容量逆序

几条值得反复咀嚼的经验：

  1. 状态定义有两大流派。「前缀长度」式（LCS、编辑距离、背包）让边界变成天然的空集情形，处理最干净；「以第 $i$ 个结尾」式（LIS）适合那些「结果依赖最后一个元素是谁」的问题。选错定义，转移会写得异常别扭。

  2. 双序列对齐问题（LCS、编辑距离）的母题思想一致：盯住两个序列的末尾字符，相同就配对缩小问题，不同就分情况各退一步取最优。掌握 LCS 后，编辑距离、最短公共超序列、字符串删除操作等一大批题都是它的变体。

  3. 二维 DP 压一维，要分清转移依赖哪几个邻居：只依赖正上方和正左方（不同路径）时，正序滚动即可；还依赖左上方（LCS、编辑距离）时，要用 prev 暂存被覆盖的左上角；0/1 背包则反过来，为防止物品重复使用，容量必须逆序遍历，这是背包最经典的坑，务必记牢。

  4. 学会做问题转化。416 看似和背包无关，一旦想到「均分等价于凑出总和一半」，立刻退化为标准 0/1 背包。DP 高手的功力，一半在写转移，另一半就在这种「把陌生问题翻译成已知模型」的洞察上。

下一节我们会进入更具挑战性的区间 DP 与树形 DP，状态和填表顺序会更加灵活，但只要你把本节这套「定义，转移，边界，填表，优化」的五步法练成本能，再难的题也能稳稳拆解。

动态规划与强化学习的关系

如果你一路看到这里，把前面讲的动态规划（DP）和后面要讲的强化学习（RL）当成了两门互不相干的课，那其实错过了最精彩的部分。它们不是“长得像”，而是“同一棵树上的两根枝条”。这一节就来把这层血缘关系一步一步讲透。

一个名字背后的故事：动态规划是谁起的名字

“动态规划”（Dynamic Programming）这个词，是数学家 Richard Bellman 在 1950 年代提出的。有个广为流传的小八卦：Bellman 当时在 RAND 公司做研究，经费由美国国防部把控，而当时的国防部长非常讨厌“研究（research）”和“数学（mathematical）”这类字眼。为了让自己的工作听起来人畜无害、又显得很有“活力”，Bellman 故意选了“dynamic”（动态的）和“programming”（这里指“规划、安排计划表”，不是写代码）这两个词。所以这个名字一开始就带着一点“伪装”的意味，它的本意其实是“分阶段做最优决策”。

记住这一点很重要：DP 从诞生第一天起，针对的就是多阶段最优决策问题，而不仅仅是我们在 LeetCode 上刷的那种“填表格”的题。RL 要解决的恰恰也是多阶段决策问题。它们师出同门，这绝非巧合。

先回顾：DP 的灵魂是什么

在前面讲 DP 时，我们反复强调过两个核心：

  • 最优子结构：一个大问题的最优解，可以由它的子问题的最优解拼出来。
  • 状态转移方程：用 dp 数组把子问题的答案存下来，靠一条递推式从小问题推到大问题。

举个最熟悉的例子，LeetCode 第 70 题“爬楼梯”（Climbing Stairs）。设 $\text{dp}[i]$ 表示爬到第 $i$ 级台阶的方法数，转移方程是

\[\text{dp}[i] = \text{dp}[i-1] + \text{dp}[i-2]\]

再看 LeetCode 第 322 题“零钱兑换”（Coin Change）。设 $\text{dp}[i]$ 表示凑出金额 $i$ 所需的最少硬币数，硬币面额集合为 $C$，转移方程是

\[\text{dp}[i] = \min_{c \in C,\ c \le i} \Big( \text{dp}[i-c] + 1 \Big)\]

注意这里多了一个 $\min$。这道题不只是“算个数量”，而是在每一步做选择（选哪个面额的硬币），并在所有选择里取最优。请把这个 $\min$ 死死记住，因为它就是连接 DP 与 RL 的那把钥匙。RL 里的“取最优动作”，本质上就是这个 $\min$ 或 $\max$。

搭桥：从 dp 表到值函数

强化学习研究的是一个智能体（agent）在环境里反复做决策的过程，标准的数学模型叫马尔可夫决策过程（Markov Decision Process，MDP）。它由这几样东西组成：

  • 状态集合 $\mathcal{S}$，当前所处的局面 $s$。
  • 动作集合 $\mathcal{A}$，可以采取的动作 $a$。
  • 转移概率 $p(s’ \mid s, a)$，在状态 $s$ 做了动作 $a$ 后，跳到 $s’$ 的概率。
  • 即时奖励 $r(s, a)$，做这个动作当场拿到的回报。
  • 折扣因子 $\gamma \in [0, 1)$，表示未来的奖励要打折，越远越不值钱。

智能体的目标是找一个策略（policy）$\pi(a \mid s)$，也就是“在每个状态下该怎么选动作”，使得从现在开始能拿到的累积折扣奖励的期望最大。

现在做一个关键的类比。在 LeetCode 的爬楼梯里，我们关心“从第 $i$ 级出发的方法数”$\text{dp}[i]$；在 RL 里，我们关心“从状态 $s$ 出发往后能拿到多少累积奖励”，这个量就叫状态值函数（state value function）$V^\pi(s)$。它的定义是

\[V^\pi(s) = \mathbb{E}_\pi \left[ \sum_{k=0}^{\infty} \gamma^k \cdot r_{t+k} \ \Big|\ s_t = s \right]\]

类似地，“从状态 $s$ 出发、先强制做动作 $a$、之后再按策略走”能拿到多少，叫动作值函数（action value function）$Q^\pi(s, a)$。

一句话对照：

\[\underbrace{\text{dp}[\,\text{状态}\,]}_{\text{DP 的填表}} \quad\longleftrightarrow\quad \underbrace{V^\pi(s)\ \text{或}\ Q^\pi(s,a)}_{\text{RL 的值函数}}\]

值函数就是一张 dp 表。 RL 里“学值函数”，本质上就是 DP 里“填 dp 数组”。区别只在于：dp 数组在 LeetCode 里是一维或二维的小数组，而值函数在 RL 里是定义在整个状态空间上的一张巨大的表。

Bellman 期望方程：DP 转移方程的 RL 版本

既然值函数是 dp 表，那它一定也满足一条“状态转移方程”。这条方程就是大名鼎鼎的 Bellman 期望方程（Bellman Expectation Equation）。我们一步一步把它推出来。

从值函数的定义出发，把求和的第一项（$k=0$）单独拎出来：

\[\begin{aligned} V^\pi(s) &= \mathbb{E}_\pi \left[ r_t + \gamma \cdot r_{t+1} + \gamma^2 \cdot r_{t+2} + \cdots \ \Big|\ s_t = s \right] \\ &= \mathbb{E}_\pi \Big[\, r_t + \gamma \big( r_{t+1} + \gamma \cdot r_{t+2} + \cdots \big) \ \Big|\ s_t = s \Big] \end{aligned}\]

仔细看括号里的那一坨 $r_{t+1} + \gamma \cdot r_{t+2} + \cdots$，它正是“从下一个状态 $s_{t+1}$ 出发的累积折扣奖励”，也就是 $V^\pi(s_{t+1})$。于是

\[V^\pi(s) = \mathbb{E}_\pi \Big[\, r_t + \gamma \cdot V^\pi(s_{t+1}) \ \Big|\ s_t = s \Big]\]

这一步是整段推导的命门：今天的值 = 今天的即时奖励 + 折扣后明天的值。 这跟爬楼梯里“$\text{dp}[i]$ 由 $\text{dp}[i-1]$ 推出来”是一模一样的递归结构，只不过 RL 里因为环境有随机性，所以外面套了一个期望 $\mathbb{E}$。

把这个期望按照“先选动作、再看环境跳到哪”展开写清楚，就得到 Bellman 期望方程的完整形式：

\[\boxed{\ V^\pi(s) = \sum_{a} \pi(a \mid s) \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \cdot V^\pi(s') \right]\ }\]

对应的动作值函数版本是：

\[\boxed{\ Q^\pi(s, a) = r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \sum_{a'} \pi(a' \mid s') \cdot Q^\pi(s', a')\ }\]

把这两条方程和零钱兑换的转移方程 $\text{dp}[i] = \min_{c}(\text{dp}[i-c] + 1)$ 摆在一起看：左边是当前状态的值，右边是即时代价（奖励）加上后继状态的值。结构完全同构。Bellman 期望方程，就是 DP 的最优子结构在 MDP 上的化身。

Bellman 最优方程：那个 $\max$ 回来了

上面的期望方程描述的是“给定一个策略 $\pi$，它的值是多少”。但 RL 的终极目标不是评价某个策略，而是要找到最好的策略。这时候，零钱兑换里那个 $\min$（在 RL 里因为是最大化奖励，所以变成 $\max$）就该登场了。

把对动作求期望 $\sum_a \pi(a\mid s)(\cdots)$ 换成“直接挑那个最好的动作”$\max_a$，就得到 Bellman 最优方程（Bellman Optimality Equation）。最优状态值函数记作 $V^$，最优动作值函数记作 $Q^$：

\[\boxed{\ V^*(s) = \max_{a} \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \cdot V^*(s') \right]\ }\] \[\boxed{\ Q^*(s, a) = r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \cdot \max_{a'} Q^*(s', a')\ }\]

看到那个 $\max_a$ 了吗？它和零钱兑换里的 $\min_c$ 是同一个东西：在所有动作（所有选择）里取最优。 这就是“最优子结构”在决策问题里最赤裸裸的体现。一旦你解出了 $Q^$，最优策略就是“每一步都贪心地选 $Q^$ 最大的那个动作”：

\[\pi^*(s) = \arg\max_{a} Q^*(s, a)\]

到这里，DP 与 RL 的血缘已经一目了然：RL 的整个数学骨架，就是把 DP 的最优子结构搬到了 MDP 上面。

三大经典算法：在已知模型时，RL 就是纯 DP

如果环境的“模型”（也就是 $p(s’\mid s,a)$ 和 $r(s,a)$）是已知的，那么 RL 退化成什么？答案是：退化成纯粹的动态规划。把上面的 Bellman 方程当作转移方程，把值函数当作 dp 表，反复迭代到收敛即可。这就是经典的三大算法。

（一）策略评估（Policy Evaluation）。 目标是“给定策略 $\pi$，算出它的 $V^\pi$”。做法是把 Bellman 期望方程当成更新公式，反复刷新整张表，直到不再变化（收敛）：

\[V_{k+1}(s) \leftarrow \sum_{a} \pi(a \mid s) \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \cdot V_k(s') \right]\]

这跟“用转移方程一轮一轮刷新 dp 数组”在做的事情没有任何本质差别。

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

def policy_evaluation(states, actions, P, R, pi, gamma=0.9, theta=1e-6):
    """策略评估：已知模型，迭代求解某个策略 pi 的状态值函数 V。
    P[s][a][s_next]: 转移概率 p(s'|s,a)
    R[s][a]:        即时奖励 r(s,a)
    pi[s][a]:       策略 pi(a|s)
    这本质上就是反复套用 Bellman 期望方程，把 V 当 dp 表刷到收敛。
    """
    V = {s: 0.0 for s in states}              # 初始化 dp 表，全部置零
    while True:
        delta = 0.0                            # 记录本轮最大变化量，用于判断收敛
        for s in states:
            v_old = V[s]
            # 套用 Bellman 期望方程：对动作求期望，对下一状态求期望
            V[s] = sum(
                pi[s][a] * (R[s][a] + gamma * sum(
                    P[s][a][s_next] * V[s_next] for s_next in states))
                for a in actions
            )
            delta = max(delta, abs(v_old - V[s]))
        if delta < theta:                      # 表格不再变化，收敛退出
            break
    return V

（二）值迭代（Value Iteration）。 目标是“直接算出最优值 $V^*$”。做法是把 Bellman 最优方程当成更新公式（注意是 $\max$ 而不是求期望）：

\[V_{k+1}(s) \leftarrow \max_{a} \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \cdot V_k(s') \right]\]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def value_iteration(states, actions, P, R, gamma=0.9, theta=1e-6):
    """值迭代：已知模型，直接迭代 Bellman 最优方程求最优值函数与最优策略。
    与策略评估唯一的区别是：内层从 '对动作求期望' 换成了 'max_a'。
    """
    V = {s: 0.0 for s in states}
    while True:
        delta = 0.0
        for s in states:
            v_old = V[s]
            # 套用 Bellman 最优方程：在所有动作里取最大（就是 LeetCode 里的那个 min/max）
            V[s] = max(
                R[s][a] + gamma * sum(P[s][a][s_next] * V[s_next] for s_next in states)
                for a in actions
            )
            delta = max(delta, abs(v_old - V[s]))
        if delta < theta:
            break
    # 收敛后，每个状态贪心地选出最优动作，得到最优策略 pi*(s) = argmax_a Q*(s,a)
    policy = {}
    for s in states:
        policy[s] = max(actions, key=lambda a:
            R[s][a] + gamma * sum(P[s][a][s_next] * V[s_next] for s_next in states))
    return V, policy

（三）策略迭代（Policy Iteration）。 在“策略评估（算出当前策略的 $V^\pi$）”和“策略改进（用 $\arg\max$ 贪心地更新策略）”之间来回交替，直到策略不再变化：

\[\pi'(s) = \arg\max_{a} \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \cdot V^\pi(s') \right]\]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def policy_iteration(states, actions, P, R, gamma=0.9):
    """策略迭代：评估 -> 改进 -> 评估 -> 改进 ... 直到策略稳定。"""
    pi = {s: {a: 1.0 / len(actions) for a in actions} for s in states}  # 初始均匀随机策略
    while True:
        V = policy_evaluation(states, actions, P, R, pi, gamma)         # 评估当前策略
        stable = True
        for s in states:
            old_action = max(actions, key=lambda a: pi[s][a])           # 旧策略下的首选动作
            # 策略改进：在当前 V 下贪心选最优动作
            best_action = max(actions, key=lambda a:
                R[s][a] + gamma * sum(P[s][a][s_next] * V[s_next] for s_next in states))
            pi[s] = {a: (1.0 if a == best_action else 0.0) for a in actions}
            if old_action != best_action:
                stable = False
        if stable:                                                      # 策略不再改变，得到最优策略
            break
    return pi, V

这三个算法都是已知模型时的精确 DP。它们和 LeetCode 上的 DP 唯一的差别，是把“一维 dp 数组”换成了“定义在状态空间上的值函数表”，把简单的递推式换成了 Bellman 方程。除此之外，思想完全一致：填表、迭代、收敛。

裂缝出现：维数灾难

既然已知模型时 RL 就是 DP，那为什么 RL 要单独成为一个庞大的领域，而不是被 DP 一口吞掉？因为现实里有两道过不去的坎。

第一道坎，叫维数灾难（curse of dimensionality）。这个词同样是 Bellman 造的。它说的是：状态空间的大小会随着维度的增加而指数级爆炸。

举个直观的例子。围棋的棋盘有 $19 \times 19 = 361$ 个交叉点，每个点有“黑、白、空”三种状态，于是合法局面的数量大约是 $3^{361}$ 这个量级，比可观测宇宙里的原子总数还多得多。你根本不可能开一个这么大的 dp 数组，光是把每个状态的值存下来都做不到，更别提逐个迭代了。

精确 DP（也就是上面那三个算法）有一个致命的前提：你得能把所有状态都枚举一遍、并为每个状态单独存一个值。 一旦状态空间大到无法枚举，查表式的精确 DP 就彻底瘫痪。

第二道坎，叫模型未知。上面三个算法都用到了转移概率 $p(s’\mid s,a)$。可是在真实世界里，你往往根本不知道这个概率。一个机器人不知道“我抬起手臂，下一秒关节会到哪个角度”的精确分布；一个下棋程序也不需要被告知对手会怎么走。Bellman 方程里那个 $\sum_{s’} p(s’\mid s,a)(\cdots)$ 求和，你根本没法算，因为你压根不知道 $p$ 是什么。

强化学习 = 近似动态规划

强化学习的全部精髓，就是用两件武器去拆解上面这两道坎。于是 RL 可以被理解为：当模型未知、或状态空间过大时的近似动态规划（approximate dynamic programming）。

武器一：用采样代替对模型的精确求和（解决“模型未知”）。

Bellman 方程里那个 $\sum_{s’} p(s’\mid s,a)(\cdots)$，本质是一个对下一状态的期望。期望算不出来怎么办？那就用样本去估计它。这正是统计里“用样本均值逼近期望”的老把戏。智能体不需要知道 $p$ 的解析形式，它只要真的去环境里走一步，环境自然会按照 $p$ 把它送到某个 $s’$，并给它一个奖励 $r$。多走几次、多采几个样本，就能把那个求和近似出来。

  • 蒙特卡洛（Monte Carlo）：跑完一整局，用实际拿到的累积奖励来估计 $V$。
  • 时序差分（Temporal Difference, TD）：不用等一整局结束，每走一步就用 $r_t + \gamma \cdot V(s_{t+1})$ 这个“一步采样的 Bellman 右端”去更新 $V(s_t)$。请注意，$r_t + \gamma \cdot V(s_{t+1})$ 正是 Bellman 期望方程的右边，只不过把“对 $p$ 求和”替换成了“真实走出来的那一个样本”。
  • Q-learning：对 Bellman 最优方程做同样的采样替换，更新公式为
\[Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \Big[\, \underbrace{r_t + \gamma \max_{a'} Q(s_{t+1}, a')}_{\text{采样版的 Bellman 最优右端}} - Q(s_t, a_t) \Big]\]
1
2
3
4
5
6
7
8

def q_learning_update(Q, s, a, r, s_next, actions, alpha=0.1, gamma=0.9):
    """Q-learning 的一步更新：模型未知，用真实采样到的 (r, s_next) 代替对 p 的求和。
    括号里就是 '采样版的 Bellman 最优方程右端'，整体是一次朝着该目标的小步修正。
    """
    td_target = r + gamma * max(Q[s_next][a_] for a_ in actions)  # 采样估计的 Bellman 目标
    td_error = td_target - Q[s][a]                                # 当前估计与目标的差距
    Q[s][a] += alpha * td_error                                   # 朝目标迈一小步
    return Q

把这一行 Q-learning 更新和前面 value_iteration 里的那一行 $\max$ 更新对照着看，你会恍然大悟：它们想做的是同一件事（逼近 Bellman 最优方程），区别只是值迭代用已知的 $p$ 做精确求和，而 Q-learning 用一个真实走出来的样本做近似。

武器二：用函数逼近代替查表（解决“维数灾难”）。

状态太多、表存不下怎么办？那就别存表了，改用一个带参数的函数去拟合它。具体来说，用一个参数为 $\theta$ 的函数 $V_\theta(s)$ 或 $Q_\theta(s, a)$ 去近似真正的值函数。当这个函数是神经网络时，就是大名鼎鼎的深度强化学习（Deep RL），比如 DQN 就是把 Q-learning 里的查表 $Q(s,a)$ 换成了神经网络 $Q_\theta(s,a)$。

函数逼近的妙处在于泛化：查表时每个状态的值是孤立存的，见过的才有值；而神经网络能从见过的状态举一反三，对从没见过的相似状态也给出合理的估计。这正是应对 $3^{361}$ 这种天文数字状态空间的唯一现实出路，你不可能把每个局面都见一遍，但你可以学一个函数去“猜”。

一句话总结

把这两件武器和 DP 的内核拼在一起，就得到了对强化学习最凝练的概括：

\[\boxed{\ \text{RL} = \text{采样} + \text{函数逼近} + \text{动态规划}\ }\]

更具体地说：

  • 动态规划提供了骨架，也就是 Bellman 方程那套“当前值 = 即时奖励 + 折扣后继值”的最优子结构。
  • 采样（蒙特卡洛、TD、Q-learning）替掉了对模型转移概率的精确求和，让我们在不知道 $p$ 的情况下也能逼近 Bellman 方程的右端。
  • 函数逼近（神经网络）替掉了查表式的 dp 数组，让我们在状态空间大到无法枚举时也能存下并泛化值函数。

所以，当你下次在 LeetCode 上写下 $\text{dp}[i] = \min_c(\text{dp}[i-c] + 1)$ 这样一行转移方程时，请记得：你写的不只是一道算法题的解，更是强化学习里 Bellman 最优方程的一个袖珍版本。DP 和 RL，从来都是同一棵树上的两根枝条。理解了这层血缘，你就握住了打通“刷题”与“训练智能体”两个世界的那把钥匙。

Mathematics, Algorithm
Tech Algorithm Classic RL
This post is licensed under CC BY 4.0 by the author.