外观
21 - 动态规划入门:从重复计算到状态转移
摘要
在网格中寻找代价最小的路径,如果逐条枚举走法,就会反复求解“怎样以最小代价到达同一个格子”。动态规划(Dynamic Programming,简称 DP)把这些子问题的答案保存下来,供后续计算复用。本文先用二维状态解释网格最小路径和,再说明计算顺序、记忆化和一维空间压缩。
1. 两个核心条件
先把大问题拆成子问题,再考虑保存哪些答案。状态是对子问题的明确描述;它必须包含后续求解所需的信息。同一个状态,无论通过哪条求解路径遇到,都应表示同一个问题。
以求最优值的问题为例,需要理解两个条件:
- 重叠子问题:不同求解分支会遇到同一个子问题。保存答案后,再次遇到它就不必重新计算。
- 最优子结构:大问题的最优解可以由相关子问题的最优解组合出来。只有这一点成立,才可以只保存子问题的最优值,而不保留所有候选方案。
网格中,如果后续合法走法只取决于当前位置,那么到达同一格子的两条路径可以接上相同的后续路径。到达代价较大的那条不会得到更小的总和,因此只需保存到达该格子的最小代价。如果题目增加了“某类格子最多经过两次”等限制,当前位置就可能不足以描述状态,还需要记录相关历史信息。
2. 网格最小路径和
给定矩形网格 grid,从左上角 (0,0) 出发,只能向右或向下移动,目标是到达右下角。路径代价是经过格子的数值之和,包含起点和终点。
先用二维表描述问题:dp[i][j] 表示从起点到达第 i 行、第 j 列的最小代价,下标从 0 开始。
对于不在第一行、第一列的格子,最后一步只能从上方 (i-1,j) 或左方 (i,j-1) 进入。这两种情况覆盖了所有合法路径;选较小的到达代价,再加上当前格子的值,就得到状态转移,也就是用已知子问题的答案计算当前答案的规则:
text
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])边界没有两个前驱,必须单独处理:
- 起点:
dp[0][0] = grid[0][0]。 - 第一行:只能从左边进入,逐格累加。
- 第一列:只能从上方进入,逐格累加。
按从上到下、每行从左到右的顺序填表,上方和左方就都已计算完成,答案是 dp[rows-1][cols-1]。这先确定了算法的含义,再考虑如何减少存储。
下面是同一转移的一维压缩实现。更新前的 dp[j] 是上方的值,dp[j-1] 是本行已经更新的左方值;详细推演见第 6.1 节。此处是方法片段,要求网格非空、各行非 null 且长度相同,并且路径累加值不超出 int 范围。
java
static int minPathSum(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int[] dp = new int[cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (i == 0 && j == 0) dp[j] = grid[i][j];
else if (i == 0) dp[j] = dp[j - 1] + grid[i][j];
else if (j == 0) dp[j] = dp[j] + grid[i][j];
else dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
}
}
return dp[cols - 1];
}每个格子仍计算一次,时间为 O(rows × cols);额外空间由二维表的 O(rows × cols) 降为 O(cols)。
3. 五步设计法
- 定义状态:每个表项回答什么问题?网格中是“从起点到这里的最小代价”。
- 列出选择:当前答案可能通过哪些情况得到?网格中最后一步来自上方或左方。
- 写出转移:如何组合前驱答案与当前代价?这里取两个前驱的较小值,再加当前格子的值。
- 确定边界:哪些状态无需转移,哪些状态不存在或不可达?起点直接赋值,第一行和第一列分别累加,不能访问越界前驱。
- 安排顺序:如何保证读取的依赖已计算?这里按行从左到右更新。
设计前还要明确输出要求:业务需要最优值、方案数量,还是一条具体方案?本文代码只返回最小代价。若要输出路径,就需要保留用于回溯的信息;若要统计方案数量,状态含义和转移规则也要相应调整。
4. 记忆化与表格法
同一套状态关系可以用两种方式计算:
- 记忆化(Memoization):从目标状态递归求依赖,算完后放入缓存;再次访问同一状态时直接返回答案。这叫自顶向下,只计算求解过程中访问到的状态,但仍要使用递归调用栈。
- 表格法(Tabulation):从初始状态出发,按依赖顺序填表,直到目标状态。这叫自底向上。上面的网格循环就是表格法,不需要递归调用栈,但必须自行安排正确的遍历顺序。
例如 Fibonacci(斐波那契)数列定义为 fib(0)=0、fib(1)=1,之后 fib(n)=fib(n-1)+fib(n-2)。直接递归求 fib(5) 时,求 fib(4) 和 fib(3) 的分支会重复求 fib(3);记忆化把它的结果缓存起来。第 6 节用这一例子展示缓存,并用网格展示填表。
5. 空间压缩的前提
空间压缩是复用不再需要的存储位置,不是改变状态含义。只有确认当前层依赖哪些先前状态,且覆盖顺序不会破坏尚未使用的值,才能压缩。
网格按行处理时,计算当前格子只用到上一行同列和当前行左列。旧 dp[j] 被读取后,可以覆盖为当前格子的值,因为它后续不再需要;左侧的新值则留给下一个格子使用。若反过来从右向左更新,左侧值仍属于上一行,就不再符合原转移。
如果需要恢复方案、解释决策或在输入变化后重算受影响状态,完整状态表可能更有用。只保留一维最优值会丢掉旧行信息,不能直接据此还原完整路径;应根据输出和排障需求决定是否压缩。
6. 完整可运行示例:记忆化与表格法
下面是完整 Java 源码,类名为 DynamicProgrammingDemo,仅使用标准库。main 调用记忆化 Fibonacci 和网格表格法。按代码推导,两行预期输出依次为 102334155 和 7。
minPath 约定空网格返回 0;与第 2 节的片段不同,它处理了行数为 0 或首行长度为 0 的情况。它仍要求输入及各行非 null、各行等长,并不负责校验所有非法输入。
java
import java.util.Arrays;
/**
* 可运行示例:动态规划入门:从重复计算到状态转移。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class DynamicProgrammingDemo {
static long fibMemo(int n) {
if (n < 0) throw new IllegalArgumentException("n must be >= 0");
// memo[x] 保存 fib(x) 的已计算结果,-1 表示尚未计算。
long[] memo = new long[n + 1];
Arrays.fill(memo, -1);
return fib(n, memo);
}
static long fib(int n, long[] memo) {
// fib(0) 和 fib(1) 是递归终点,不能继续拆分。
if (n < 2) return n;
// 命中缓存后立即返回,避免再次展开相同递归子树。
if (memo[n] != -1) return memo[n];
// 先求依赖状态,再把本状态写入缓存供其他分支复用。
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
static int minPath(int[][] grid) {
// 空网格没有可走路径,约定代价为 0。
if (grid.length == 0 || grid[0].length == 0) return 0;
// dp[j] 在更新前表示上方单元格,更新后表示当前行当前列。
int[] dp = new int[grid[0].length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < dp.length; j++) {
if (i == 0 && j == 0) {
// 起点没有前驱,代价就是自身权重。
dp[j] = grid[i][j];
} else if (i == 0) {
// 第一行只能从左侧到达。
dp[j] = dp[j - 1] + grid[i][j];
} else if (j == 0) {
// 第一列只能从上方到达;旧 dp[j] 正是上方的最优值。
dp[j] += grid[i][j];
} else {
// 旧 dp[j] 来自上方,dp[j-1] 是本行刚更新的左方。
dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
}
}
}
return dp[dp.length - 1];
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
System.out.println(fibMemo(40));
System.out.println(
minPath(new int[][] { { 1, 3, 1 }, { 1, 5, 1 }, { 4, 2, 1 } })
);
}
}6.1 手工推演:一维数组为什么没有丢信息
网格为:
text
1 3 1
1 5 1
4 2 1逐行更新 dp:
| 处理阶段 | dp | 含义 |
|---|---|---|
| 第一行结束 | [1, 4, 5] | 起点到第一行各位置的唯一走法 |
| 第二行结束 | [2, 7, 6] | 到 (1,2) 选择从上方的 5 进入 |
| 第三行结束 | [6, 8, 7] | 终点最小路径和为 7 |
更新 (i,j) 时,只需要“上方旧值”和“左方新值”,所以保存整张二维表不是必要条件。这也是空间压缩成立的依赖依据。
6.2 正确性不变量
不变量是算法在指定阶段始终成立的性质。这里,在第 i 行第 j 列更新后,dp[0..j] 保存当前行对应位置的最小代价;当 i > 0 时,dp[j+1..] 仍保存上一行对应位置的最小代价。第一行尚未更新的位置只是数组初值,代码不会把它们当作有效前驱。
起点赋值建立边界,第一行和第一列分别使用唯一前驱。其余格子更新时,上方旧值与左方新值都已是各自的最优值;取较小值并加当前代价,就保持了不变量。逐格更新到终点后,最后一个表项因此是整个问题的最优值。
6.3 复杂度与适用边界
- 网格算法访问每个格子一次,时间
O(rows × cols),额外空间O(cols)。 - 记忆化 Fibonacci 的非边界状态首次计算后会被缓存,边界状态直接返回;总时间为
O(n),缓存和递归调用栈各占O(n)空间。记忆化消除了重复展开,但没有消除递归深度带来的栈限制。 long的 Fibonacci 从fib(93)起溢出;示例用于解释记忆化,不适合任意精度计算。- 若路径允许向四个方向移动,状态依赖可能形成环,不能直接按行填表,通常要转为最短路问题。
- 建议测试:空网格、单格、单行、单列、负权值(仅右/下且无环时仍可计算)、大权值溢出。
7. DP、DAG 与最短路的关系
把状态看作顶点,从被依赖的状态向当前状态连边,就得到一张有向图。**有向无环图(DAG)**指不存在沿箭头绕回原点的路径;拓扑顺序则保证每条边的起点都先于终点处理。依赖无环时,就能按这样的顺序计算状态。
只向右、向下的网格就是不必显式建图的 DAG:每次移动都会增大行号或列号,不可能回到原格子。按行填表因此满足依赖顺序。
最短路中的松弛是用一条候选路径尝试改进当前距离。一般图可能有环,算法要根据边权和约束选择:无权图或边权相同且为正的图可使用广度优先搜索(BFS),非负边权图可用基于优先队列的 Dijkstra,允许负边权时还需要考虑多轮松弛及负环问题。不能把网格的一次填表顺序直接套到一般图上。
若状态转移形成环,应先分析模型是否属于一般最短路,或者是否需要反复更新直到状态稳定的固定点迭代。后者还需单独说明迭代为何能收敛;有循环依赖本身并不保证能得到答案。
8. 验证与排障
- 对小网格枚举所有右/下路径,作为答案基线,再比较二维表格法与一维压缩结果。记忆化实现也可用于对照,但若共享同一条错误转移,结果一致仍不能证明正确。
- 结果异常时,先把每个状态的含义写清,再逐格检查起点、第一行、第一列和覆盖顺序。
- 若扩展模型含不可达状态,使用明确的哨兵值,即专门表示不可达的标记。转移前先判断可达性,避免把哨兵当作真实代价相加而溢出。
- 性能异常时,记录状态数、转移次数;记忆化还可记录缓存命中率和最大递归深度,以区分重复计算、状态过多和调用栈过深。
9. 容易踩的坑
- 状态遗漏会影响后续选择的信息,导致本不等价的子问题共用答案。
- 在含不可达状态的模型中一律初始化为 0,把不存在的路径当作合法最优值。
- 依赖尚未算出就读取,或压缩时提前覆盖仍要使用的旧值。
- 使用
int累加巨大代价,溢出后比较出的“最小值”失去意义。 - 看到递归就加缓存,却没有重复子问题可供复用。
10. 总结
动态规划是把重复子问题命名为状态,并按依赖关系保存和复用答案。
- 状态定义比转移公式更重要。
- 初始化和遍历顺序属于正确性的一部分。
- 空间压缩必须建立在依赖范围清晰的前提上。