动态规划入门：最优子结构与状态转移

FreeGuideOnline 最新 2026-06-18

什么是动态规划

动态规划（Dynamic Programming，简称DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它的核心思想非常朴素：记住已经解决过的子问题的解，避免重复计算。

很多初学者会被“动态规划”这个名称吓到，但实际上它并不是一种神秘的算法，而是一种用空间换时间的优化策略。当你发现一个问题需要反复求解相同的子问题时，就可以考虑使用动态规划。

要掌握动态规划，你必须理解两个最核心的概念：最优子结构 和 状态转移。

最优子结构：问题的“完美基因”

什么是子结构

子结构指的是原问题可以被拆解成的、规模更小的同类问题。打个比方，如果你要计算从北京到广州的最短路径，这个问题可以拆解为“从北京到武汉的最短路径”加上“从武汉到广州的最短路径”。这里，“北京-武汉”和“武汉-广州”就是原问题的子结构。

最优子结构的定义

当一个问题的最优解包含其子问题的最优解时，我们就称该问题具有最优子结构性质。换句话说，全局的最优决策一定是由局部的最优决策组合而成的。

可以这样理解：假设你要爬上一座高山，你会选择一条最优路线。无论你从山脚走到山腰的哪一点，从这一点出发到山顶，你所走的必然也是从该点出发到山顶的最优路线。如果存在一条更优的“山腰-山顶”路线，你之前选的路线就不是全局最优的——这就自然蕴含了最优子结构。

如何判断一个问题是否具有最优子结构

判断的关键在于：能否在不依赖未来决策的情况下，通过子问题的最优解构造出原问题的最优解。

经典反例是“最长简单路径”问题（不允许重复经过节点的最长路径）。在带环的图中，最长简单路径不具有最优子结构，因为子问题的最优路径可能会与父问题的最优路径产生冲突（比如重复经过节点），导致无法直接拼接。

而“最短路径”问题则具有最优子结构，因为如果A到C的最短路径经过B，那么A到B的路径和B到C的路径都必然是最短的。我们可以放心地拼接它们。

状态与状态转移

什么是状态

状态是动态规划中最关键的抽象。它是对某一时刻（或某一阶段）子问题解的描述。一个状态通常对应一个或多个决策变量，比如在背包问题中，状态可以定义为 dp[i][w]：考虑前 i 个物品，背包容量为 w 时能获得的最大价值。

定义一个清晰的状态，需要明确两件事：

这个状态代表什么含义？
哪些参数可以唯一确定一个子问题？

状态转移方程：问题的递推引擎

状态转移方程描述了当前状态是如何从更小的子状态推导出来的。它是将最优子结构用数学语言精确表达出来的方式。

一个典型的状态转移方程通常长这样：

dp[state] = optimal_choice(dp[prev_state_1] + cost_1, dp[prev_state_2] + cost_2, ...)

其中 optimal_choice 根据问题取最大值或最小值。这个方程直接体现了“全局最优由局部最优组合而成”的思想。

从零到一：斐波那契数列中的动态规划思想

让我们通过一个最简单的例子来感受状态和转移。斐波那契数列的定义是 F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。

识别最优子结构（本例为子结构）

尽管斐波那契数列不存在“选择最优”的过程，但它具有非常清晰的自相似子结构：F(n) 的解完全依赖于 F(n-1) 和 F(n-2) 的解。这些子问题之间没有重叠的约束冲突，可以无脑拼接。

定义状态

我们可以定义一个一维状态 dp[i]，表示第 i 个斐波那契数的值。

写出状态转移方程

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

这就是最原始的状态转移方程。边界条件（初始状态）是 dp[0]=0, dp[1]=1。

计算顺序与记忆化

如果我们直接从 n 开始递归，会带来指数级的重复计算。动态规划的做法是自底向上：从 dp[0] 和 dp[1] 开始，依次计算出 dp[2]、dp[3]……直到 dp[n]。由于每个状态只计算一次，时间复杂度从 O(2^n) 降到了 O(n)。

对于初学者，建议始终先定义好状态数组的含义，再在纸上写出几个小规模情况的推导过程，最后归纳出状态转移方程。

实战解析：经典的“爬楼梯”问题

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

1. 验证最优子结构

爬到第 i 阶的方法数，只依赖于爬到第 i-1 阶的方法数（再走1步）和爬到第 i-2 阶的方法数（再走2步）。子问题的方法数之间相互独立，直接叠加即可得到全局解。该问题具有完美的子结构性质。

2. 定义状态

设 dp[i] 为爬到第 i 阶楼梯的方法总数。

3. 推导状态转移方程

要想到达第 i 阶，最后一步只有两种可能：

从第 i-1 阶爬 1 步上来，对应的方法数为 dp[i-1]。
从第 i-2 阶爬 2 步上来，对应的方法数为 dp[i-2]。

因此状态转移方程为：

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

4. 确定边界条件

dp[0] = 1：地面（第0阶）只有一种方法，就是站着不动。
dp[1] = 1：到达第1阶只有爬1个台阶这一种方法。

5. 代码实现与空间优化

按照状态转移方程，我们可以写出以下自底向上的代码（伪代码示例）：

function climbStairs(n):
    if n <= 1: return 1
    dp[0] = 1
    dp[1] = 1
    for i from 2 to n:
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

进一步观察发现，dp[i] 只依赖于前两个状态，因此我们可以用两个变量滚动更新，将空间复杂度优化至 O(1)。这种优化技巧在动态规划中非常常见，但初学者应先专注于写出正确的状态定义和转移方程，优化是锦上添花的事情。

深度理解：硬币找零问题

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

最优子结构分析

假设我们知道凑出金额 amount - coin 的最少硬币数（coin是某一枚硬币的面额），那么凑出 amount 的最少硬币数就是在所有可能的硬币选择中，选出 dp[amount - coin] + 1 的最小值。这就是非常典型的一个最优子结构：大金额的最优解依赖于小金额的最优解。

状态定义

dp[a]：凑出金额 a 所需的最少硬币数量。

状态转移方程

dp[a] = min(dp[a - coin] + 1)  对于每一个 coin 满足 a >= coin

初始条件：dp[0] = 0（凑出0元不需要硬币）。对于无解的状态，我们可以用一个极大值（如 amount+1）表示无法凑出。

计算顺序与遍历要点

外层循环从 1 到 amount 遍历所有金额，内层循环遍历所有硬币面额。对于每个金额，我们尝试“最后一枚硬币是哪种”，并取出最小硬币数。这种“逐个推进状态，每个状态尝试所有可能的前置决策”的模式，是初学动态规划最值得掌握的思维框架。

如何系统性地构造动态规划解法

很多教程直接给出状态转移方程，让初学者感到无从下手。下面是一个可复用的四步思考法，帮助你从零开始构建任何DP解法：

定义状态空间，明确状态含义
问自己：我需要知道什么信息才能描述一个子问题？这些信息中哪些是变化的参数？将这些参数组合成一个状态。一开始可以贪心一点，先定义高维状态，等透彻理解后再优化。
拆解最后一步，寻找子问题
想象已经走到原问题的最后一步，思考这最后一步有哪些可能的“选择”。每一种选择都会将原问题规约到一个规模更小的子问题。这正是最优子结构的体现：原问题的最优解 = 这些选择中最优的那个。
写出状态转移方程
基于第二步的拆解，用数学表达式描述当前状态和子状态之间的关系。注意标注好边界条件（最小的子问题是什么，它们的解是什么）。
确定计算顺序与实施
画出状态之间的依赖图（通常是一个有向无环图）。确保在计算某个状态时，它所依赖的所有子状态都已经预先计算好了。自底向上的迭代通常是最高效的选择。

常见误区与诊断

把状态定义得过于“贪心”
例如在股票买卖问题中，如果只定义 dp[i] 为第 i 天的最大利润，你会发现无法处理“当前是否持有股票”这个关键信息。此时必须在状态中增加维度（如 dp[i][0] 表示未持有，dp[i][1] 表示持有）。
忽略子问题的独立性
如果一个子问题的解会因父问题的不同决策而改变，那么该问题不满足最优子结构，不能直接使用动态规划。此时或许需要增加状态维度，或者换用其他算法。
遍历顺序混乱
状态转移方程本身并不包含“先算谁后算谁”的信息，但错误的计算顺序会导致使用的子状态尚未被计算。永远根据状态的依赖关系来规划计算流程，必要时可以画一张依赖图。

结语

动态规划的内核其实非常简单：找到一种方式将问题分解为互相独立的子问题，并找出当前状态与已求解的子状态之间的递推关系。最优子结构给了你分解问题的信心，状态转移方程则是你落实这一信心的具体工具。

掌握这两个概念后，后续学习的记忆化搜索、区间DP、树形DP、状压DP等高级主题，本质上不过是在不同的问题结构上应用同样的思想。因此，在初学阶段，请花足够的时间反复练习定义状态和推导转移方程，直到它能成为一种思维本能。