数据结构与算法 / 系统课时
动态规划适用条件
动态规划适用条件
动态规划不是“看到递归就建数组”,而是一套把重复状态只计算一次的方法。本课建立一套判断框架:先确认状态能否完整描述问题,再检查子问题是否重复、转移是否无环,以及局部最优能否组成整体最优。
学习目标
- 判断一个问题是否具备可定义状态、重复子问题和有效状态转移。
- 区分递归、记忆化搜索与自底向上动态规划。
- 识别无后效性、最优子结构和状态设计中的常见陷阱。
判断框架
一个问题适合动态规划,通常需要同时回答四个问题。
- 能否用有限参数定义状态,例如
dp[i]或dp[i][j]? - 当前状态能否由规模更小的状态转移得到?
- 不同求解路径是否会反复到达同一状态?
- 状态是否已经包含影响未来决策的全部信息?
对于最优化问题,还要检查最优子结构:整体最优解能否由子问题的最优解组合而成。若某个决策会依赖未记录的历史信息,就需要扩充状态,而不是直接套用原转移。

三个关键条件
重复子问题
递归树中同一个参数组合被多次求值,才有缓存价值。若所有子问题都只出现一次,分治通常已经足够,额外的状态表反而增加空间和实现成本。
无后效性
一旦状态确定,未来结果不应再依赖状态之外的完整历史。例如路径问题若受“已经访问过哪些节点”影响,就必须把访问集合纳入状态,或改用其他算法。
最优子结构
对最优化问题,最优解中的子结构也应当是对应子问题的最优解。最长简单路径通常不具备容易利用的最优子结构,因为子路径选择会互相限制;最短路径在边权满足相应条件时则可以利用。
| 方法 | 是否缓存 | 计算顺序 | 适合场景 |
|---|---|---|---|
| 直接递归 | 否 | 按调用树展开 | 子问题不重复或规模很小 |
| 记忆化搜索 | 是 | 自顶向下,只访问需要的状态 | 状态稀疏、转移自然递归 |
| 自底向上 DP | 是 | 按依赖顺序填表 | 状态密集、顺序明确、便于压缩空间 |
完整可运行示例
斐波那契数列不是最优化问题,但它能清楚展示“状态可定义、递推关系明确、子问题大量重复”这三个条件。下面的 Java 17 程序比较直接递归、记忆化搜索和自底向上计算的调用次数与结果。
import java.util.Arrays;
public class DynamicProgrammingConditionsDemo {
private static long naiveCalls;
private static long memoCalls;
static long fibNaive(int n) {
naiveCalls++;
if (n <= 1) {
return n;
}
return fibNaive(n - 1) + fibNaive(n - 2);
}
static long fibMemo(int n, long[] memo) {
memoCalls++;
if (n <= 1) {
return n;
}
if (memo[n] != -1) {
return memo[n];
}
// 每个 n 的结果只计算一次,后续调用直接复用。
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
static long fibBottomUp(int n) {
if (n <= 1) {
return n;
}
long previous = 0;
long current = 1;
for (int i = 2; i <= n; i++) {
// 当前状态只依赖前两个状态,因此可以把数组压缩为两个变量。
long next = previous + current;
previous = current;
current = next;
}
return current;
}
public static void main(String[] args) {
int n = 10;
long naiveResult = fibNaive(n);
long[] memo = new long[n + 1];
Arrays.fill(memo, -1);
long memoResult = fibMemo(n, memo);
long bottomUpResult = fibBottomUp(n);
System.out.println("n = " + n);
System.out.println("直接递归: result = " + naiveResult + ", calls = " + naiveCalls);
System.out.println("记忆化搜索: result = " + memoResult + ", calls = " + memoCalls);
System.out.println("自底向上: result = " + bottomUpResult);
}
}运行命令:
javac DynamicProgrammingConditionsDemo.java
java DynamicProgrammingConditionsDemo预期输出
n = 10
直接递归: result = 55, calls = 177
记忆化搜索: result = 55, calls = 19
自底向上: result = 55结果相同,但记忆化搜索避免了大量重复调用。自底向上版本进一步利用“只依赖前两个状态”的性质,把空间从 压缩到 。
Tips、常见错误与练习
- 先写出状态含义,再写转移方程。若一句话无法准确解释
dp[i][j]表示什么,状态通常还没有设计清楚。 - 有递推式不等于必须使用动态规划;没有重复子问题时,缓存不会降低渐进时间复杂度。
- 转移依赖必须形成可计算顺序。若状态之间存在未处理的环,应重新定义状态、增加迭代收敛过程,或改用图算法。
- 不要把贪心选择误认为最优子结构。贪心还要求局部最优选择可以安全地提前确定,条件比动态规划更强。
练习 1:统计爬楼梯问题中直接递归和记忆化搜索的调用次数。输入 n = 20,验收条件是两种方法结果一致,且记忆化调用次数随 n 线性增长。
练习 2:判断“区间内最大值查询”“0-1 背包”“归并排序”是否需要动态规划。对每个问题写出状态或子问题定义,并说明是否存在重复子问题,不能只给出是或否。
本课总结
- 动态规划的核心是定义可复用状态,并按合法依赖关系只计算一次。
- 重复子问题决定缓存是否有价值,无后效性决定状态是否完整。
- 最优化问题还需满足最优子结构;条件不满足时应扩充状态或更换算法。
下一课预告
下一阶段将进入状态设计与转移方程,学习如何从业务约束中提取维度、初始化边界,并选择记忆化或自底向上的计算顺序。