动态规划状态转移方程推导方法

可视化演示

展示DP表格自底向上填充过程，绿色高亮当前填充格子，箭头标注状态依赖方向，支持切换查看转移方程和空间优化

状态定义与子问题划分

盖大楼之前，工程师最重要的工作不是搬砖，而是翻开空白图纸，回答一个看似简单的问题：每一层楼用来做什么？有的楼层是机房，有的是餐厅，有的是会议室。功能不明确，承重墙、水电、电梯全都无从谈起。动态规划的第一步也是这个：定义“状态”——你要在表格 dp 的每一个格子里记录什么东西。

在代码里，“状态”通常写作 dp[i] 或 dp[i][j]，它描述的是“原问题拆出来的某个子问题的答案”。比如“前 i 个元素能组成的最大价值”就是一个常见状态。而“子问题划分”就是把大问题切成互相重叠的小问题。划分要满足三个性质：最优子结构——大问题的最优解里藏着子问题的最优解；重叠子问题——不同路径会反复遇到同一个子问题；无后效性——子问题一旦算出，就不会被未来的选择改变。

$$\displaystyle dp[i] = \text{前 } i \text{ 个元素的最优值}$$

1. dp 符号：这是 dynamic programming 的缩写，代表整个动态规划表格，表格里每一格都是一个小问题的答案。

$$dp$$

2. 下标 i：方括号里的 i 表示“前 i 个元素”，它是状态的第一维，告诉我们在处理原问题的哪个切片。

$$[i]$$

3. 最优值：根据题意，这格可以存最大值、最小值、方案数或布尔值，它定义了“答案长什么样”。

$$\text{最优值}$$

楼层功能图一旦画定，后续所有承重设计都依附于它。同理，状态定义是整个 DP 的地基——很多初学者写不出转移方程，不是因为不会递推，而是因为状态定义本身就是模糊的。所以，拿到题目先别急着写代码，花几分钟把 dp 的含义写在纸上，这是最值得的投资。

状态转移方程推导

楼层功能确定后，工程师开始问下一个问题：这一层的楼板压在哪些楼下承重墙上？重量如何传递？动态规划中，这个“压力如何传递”就是状态转移方程（state transition equation）。它的任务是把大状态拆成小状态的组合：dp[i] 等于某些更小的 dp[k] 经过加减、取 min 或 max 后的结果。

推导方程有三个屡试不爽的思维工具。第一，最后一步分析法：假设问题已经解决，倒推“最后一步我做了什么决策”。第二，分类讨论：把最后一步的所有可能选择列出，为每个选择写一个子表达式，再统一取最优或求和。第三，验证正确性：用最小的例子手工跑一遍，与暴力答案比对。以 0-1 背包为例——每一件物品只有“装”与“不装”两种决策：

$$\displaystyle dp[i][j] = \max\left(dp[i-1][j], \; dp[i-1][j - w_i] + v_i\right)$$

1. dp[i][j] 的含义：表示前 i 件物品、背包容积为 j 时能装下的最大价值，是二维状态表的一个单元格。

$$dp[i][j]$$

2. 不装的子方案：dp[i-1][j] 表示干脆跳过第 i 件物品，直接沿用只考虑前 i-1 件时的最优结果。

$$dp[i-1][j]$$

3. 装入的子方案：dp[i-1][j-w_i] 是给第 i 件物品腾出 w_i 重量后，前 i-1 件物品剩下的最优价值，再加 v_i。

$$dp[i-1][j - w_i] + v_i$$

4. 取最大值：max 把两种决策中价值更高的那个选出来，作为当前格子的答案。

$$\max(\cdot)$$

承重方案在图纸上被反复验算后，大楼的骨架就定型了。状态转移方程也一样，它是整个 DP 的灵魂——写出来，算法就完成了一半。后续的循环、缓存、优化，都是围绕这个式子展开的细节工作。

自顶向下记忆化

图纸设计好之后，经验丰富的老工程师会先做“逆向验算”：从顶楼开始，一层层往下追问“这层靠什么撑住？”每问完一层，就在笔记本上记一笔。如果发现某个下层结构以前验算过，直接翻开笔记本抄答案，绝不再算第二遍。这就是自顶向下记忆化（memoization）：从大问题出发递归拆解，用小本本（缓存）记住算过的子问题。

实现记忆化只需要三件套：递归函数对应状态定义；基准情形作为递归出口；缓存数组或哈希表在每次递归开头查一下——命中就直接返回，没命中才计算并存入缓存。以斐波那契数列为例，它的每一层都只依赖紧邻的前两层：

$$\displaystyle F(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F(n-1) + F(n-2) & n \geq 2 \end{cases}$$

1. 基准情形 n=0：F(0)=0 是递归的第一块地基，表示数列的第一项，不需要再拆。

$$F(0)=0$$

2. 基准情形 n=1：F(1)=1 是第二块地基，递归拆到 n=1 时直接返回 1。

$$F(1)=1$$

3. 递推分支 n≥2：F(n-1)+F(n-2) 把当前层拆成紧邻的两个子层，递归继续向下。

$$F(n-1)+F(n-2)$$

有了笔记本，每一层只真正计算一次，重复的楼层直接抄旧答案。这就是“记忆化”三个字的含义——用记忆换时间。它的最大优势是“按需计算”：只有被递归路径触及的子问题才会被求解，在依赖关系稀疏的问题上特别省力。

自底向上迭代

逆向验算只是检查，真正开工时，工程队不会从顶楼往下浇混凝土。他们从地基开始，逐层向上，每层浇筑完立刻成为下一层的支撑，秩序井然。这就是自底向上迭代（bottom-up）：先填最小的子问题，再用 for 循环逐格填表，让每个状态在被需要之前就已经准备就绪。

与记忆化相比，自底向上的优势很明显：没有递归的函数调用栈开销，不会在大数据规模下爆栈；循环访问连续内存，更符合 CPU 缓存友好。代价是要老老实实把表填完，哪怕某些状态最后没有用到。斐波那契的迭代版本就是一行朴素递推：

$$\displaystyle dp[i] = dp[i-1] + dp[i-2], \quad i = 2,3,\ldots,n$$

1. 循环起点 i=2：因为 dp[0] 与 dp[1] 已经手动填好，递推从第 2 格开始。

$$i=2$$

2. 相邻子状态求和：dp[i-1]+dp[i-2] 表示当前格由前面紧挨的两格直接相加得到。

$$dp[i-1]+dp[i-2]$$

3. 推进到 n：循环不断右移，直到目标下标 n 被填出，答案就是这一格。

$$i=n$$

真实盖楼虽然不偷懒，但每一层都扎实；迭代虽然可能多算几个无关状态，但它稳定、可控，是工程上最常用的实现方式。在面试和竞赛中，除非题目明确需要“按需计算”，否则优先考虑自底向上。

空间优化滚动数组

大楼盖到封顶，项目经理来复盘：储藏室里堆着从地基到顶层的全部图纸，但盖每一层时，其实只需要最近的两三张。于是大家把用过的旧图纸送去碎纸，只保留一个滑动的“图纸窗口”。这就是滚动数组（rolling array）：把二维 dp 表压缩成一两个一维数组，反复复用，空间从 O(n×m) 降到 O(m)。

以 0-1 背包为例，二维表压缩成一维后，递推式变成 dp[j] = max(dp[j], dp[j-w_i]+v_i)。但这里有一个非常容易踩的坑：内层容量循环必须倒序遍历。因为正序会让“刚刚算出的新值”混进“上一层的旧值”里，就像盖第 5 层时误用了第 5 层自己的图纸，楼层必然错位。

$$\displaystyle dp[j] = \max\left(dp[j], \; dp[j - w_i] + v_i\right) \quad (j \text{ 从大到小})$$

1. 等号右侧的 dp[j]：更新前它存的是上一层（前 i-1 件物品）的旧值，代表“不装第 i 件”。

$$dp[j]$$

2. 装入旧值：dp[j-w_i]+v_i 里的 dp[j-w_i] 同样必须是上一层的旧值，倒序恰好保证它还没被覆盖。

$$dp[j - w_i] + v_i$$

3. 倒序条件：j 从 capacity 递减到 w_i，从大容量往小容量扫，确保小容量旧值不被提前覆盖。

$$j:\ capacity \to w_i$$

碎掉旧图纸，楼照盖不误；滚动数组牺牲一点对“历史层”的保留，换来空间的大幅节省，是 DP 优化的第一课。理解倒序原理后，你会发现“完全背包”问题里把内层循环改成正序，反而正好利用了“新值可复用”的特性——这就是滚动数组的妙处。

初始化与边界条件

任何一栋楼都少不了一样东西：地基。图纸上画得再宏伟，地基不牢，第一层浇筑就会塌方。在动态规划里，地基就是初始化（initialization）与边界条件（boundary condition）：给最小的子问题赋值，并处理递推过程中“下标越界”的访问。初始化错一个数字，整张表从第一层开始就歪了。

初始化的设计有两条经验法则。第一，求最小值时，非法状态（不可达的状态）要初始化为正无穷，这样 min 操作会自动忽略它；求最大值时则相反，初始化为负无穷。第二，计数类问题的基准通常是 1（空方案也算一种方案）。以下是一种常见写法：

$$\displaystyle dp[i] = \begin{cases} 0 & i = 0 \\ +\infty & i \neq 0 \end{cases}$$

1. 基准 i=0：dp[0]=0 是唯一的合法起点，表示空集或零容量的代价为 0。

$$dp[0] = 0$$

2. 非法状态：i≠0 时设为 +∞，表示这些状态在递推开始前还没被“够到”。

$$+\infty$$

3. min 的自动过滤：因为 +∞ 参与 min 运算时永远大于有限值，非法状态自然被排除。

$$\min(dp[i], dp[j]+\text{cost})$$

地基浇筑时多一厘米偏差，顶层就会偏出几米。初始化与边界条件就是 DP 的地基，值得在最开始花时间仔细推敲。写代码前，问自己三个问题：最小的子问题答案是什么？哪些状态从起点不可达？递推时下标会不会越界？想清楚再动手。

经典DP问题应用

同一套“盖楼方法论”，可以盖出功能完全不同的楼：住宅楼是斐波那契数列——每一层只靠下面两层；仓库是 0-1 背包——每一格都要权衡“装或是不装”；写字楼是最长公共子序列（LCS）——两个序列像两栋楼并肩而立，逐层比对。经典问题各有各的状态设计，但追根溯源都离不开那套推导流程。

以 LCS 为例：dp[i][j] 表示字符串 a 的前 i 个字符与字符串 b 的前 j 个字符的最长公共子序列长度。逐字符比对时，当前字符相同就继承左上角结果加一；不同就取上方和左方的较大值：

$$\displaystyle dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & a_i = b_j \\ \max\left(dp[i-1][j], \; dp[i][j-1]\right) & a_i \neq b_j \end{cases}$$

1. 匹配分支：当 a_i = b_j 时，说明当前字符可以连进公共子序列，长度等于“左上角 + 1”。

$$dp[i-1][j-1] + 1$$

2. 不匹配分支：a_i ≠ b_j 时，当前字符无法同时入选，只能继承上方或左方较长的一个结果。

$$\max\left(dp[i-1][j], \; dp[i][j-1]\right)$$

3. 两类覆盖：每对字符只有“相等 / 不等”两种可能，两个分支合起来覆盖全部情况。

$$a_i = b_j \;\text{ or }\; a_i \neq b_j$$

住宅、仓库、写字楼，外形千差万别，但建造流程同源。经典 DP 问题练的就是这份“从问题到状态”的迁移能力。当你把斐波那契、背包、LCS 都亲手实现一遍，再遇到新问题，自然会问：它的“楼层”是什么？“承重”怎么传？

完整思维流程

最后，总设计师把这套方法论沉淀成一份标准作业流程：接需求、定功能、算承重、验地基、动工、省材料。动态规划的开发也是一条流水线——分析问题、定义状态、推导方程、确立边界、优化实现。五步走完，一份 DP 题解就诞生了。

其中最关键的是前两步：分析问题时要判断有没有最优子结构和重叠子问题；定义状态时要选好维度、说清 dp 的含义。之后推导方程便水到渠成。把整个方法论压缩成一个通用模板，就是“当前状态 = 所有前驱选择中的最优者”：

$$\displaystyle dp[\text{state}] = \min_{k \in \text{choices}} \Big( dp[\text{prev}_k] + \text{cost}(k) \Big)$$

1. 当前状态 state：这是我们要计算的格子，代表一个子问题的答案。

$$dp[\text{state}]$$

2. 决策集合 choices：最后一步所有可能的选择，如装/不装、向左/向右、匹配/不匹配。

$$k \in \text{choices}$$

3. 前驱状态 prev_k：做出决策 k 之前必须先处于的那个状态，是“上一层”的某个格子。

$$dp[\text{prev}_k]$$

4. 转移代价 cost(k)：从 prev_k 走到当前状态付出的代价或收益，如物品价值、一步距离。

$$\text{cost}(k)$$

总设计师的流程一旦固化，面对任何新楼型都能按部就班出图。对 AI 从业者来说，“状态→转移→边界→优化”这套思维，也是从刷题到真实建模的分水岭——无论是训练序列模型还是设计强化学习奖励，本质上都在做同一件事：把问题拆成可递推的层。

AI 应用场景

Python 演示

def knapsack(weights, values, capacity):    """    0-1 背包：自底向上迭代 + 滚动数组空间优化    weights: 每件物品重量    values: 每件物品价值    capacity: 背包容量    返回: 最大价值    """    n = len(weights)    dp = [0] * (capacity + 1)          # 滚动数组，只保留一维    for i in range(n):                 # 外层遍历物品        w, v = weights[i], values[i]        # 内层倒序遍历容量，防止本轮新值污染后续状态        for c in range(capacity, w - 1, -1):            dp[c] = max(dp[c], dp[c - w] + v)    return dp[capacity]  def knapsack_full(weights, values, capacity):    """二维版本：保留完整决策表，并回溯最优选择"""    n = len(weights)    dp = [[0] * (capacity + 1) for _ in range(n + 1)]    for i in range(1, n + 1):        w, v = weights[i - 1], values[i - 1]        for c in range(capacity + 1):            if c >= w:                dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - w] + v)            else:                dp[i][c] = dp[i - 1][c]    # 回溯选取的物品：比较当前格与上一格是否变化    chosen = []    c = capacity    for i in range(n, 0, -1):        if dp[i][c] != dp[i - 1][c]:            chosen.append(i - 1)            c -= weights[i - 1]    chosen.reverse()    return dp[n][capacity], chosen  if __name__ == "__main__":    weights = [2, 3, 4]    values = [3, 4, 5]    capacity = 5    best, items = knapsack_full(weights, values, capacity)    print("最大价值:", best)    print("选中物品编号(从0开始):", items)    print("滚动数组结果:", knapsack(weights, values, capacity))

1. dp = [0] * (capacity + 1)滚动数组只保留一维，相当于“碎掉旧图纸只留最近一层”。
2. for c in range(capacity, w - 1, -1):内层倒序遍历容量，确保读取 dp[c-w] 时还是上一层的旧值。
3. dp[c] = max(dp[c], dp[c - w] + v)状态转移方程的落地，等价于“不装”与“装”两种情况取优。
4. dp = [[0] * (capacity + 1) for _ in range(n + 1)]二维表保留所有子问题答案，方便回溯。
5. if dp[i][c] != dp[i - 1][c]:判断当前格是否由“装入第 i 件”产生，若是则记录并腾出容量。

常见误区

面试题