数据结构与算法 / 系统课时
动态规划的状态设计
动态规划的状态设计
动态规划代码是否正确,首先取决于状态是否定义清楚。本课用网格最小路径和演示完整设计过程:一句话确定状态含义,从最后一步推导转移方程,再根据依赖关系安排初始化和遍历顺序。
学习目标
- 用完整语句定义状态含义、范围和最终答案位置
- 从当前状态的可选前驱推导转移方程
- 正确处理边界初始化、遍历顺序和输入约束
状态定义决定整个算法
设 cost[row][column] 是网格代价,只允许向右或向下移动。定义 dp[row][column] 为“从左上角走到当前位置的最小路径和”。这句话同时确定了二维数组的两个维度、右下角是最终答案、当前格代价必须计入,以及前驱只能来自上方和左方。
到达内部位置的最后一步只有两种可能,因此转移方程为:
dp[row][column]
= min(dp[row - 1][column], dp[row][column - 1])
+ cost[row][column]若状态改成“路径数量”,合并方式会由 min 变为加法;若改成最大收益,则会变为 max。转移运算必须与问题目标一致。

初始化与遍历顺序
左上角没有前驱,因此 dp[0][0] = cost[0][0]。第一行只能从左侧到达,第一列只能从上方到达,它们是通用转移方程无法覆盖的边界状态。完成这些初始化后,内部位置才能统一使用同一条方程。
计算当前格前,上方和左方状态必须已经得到结果,所以应按行从上到下、每行从左到右遍历。无后效性并不表示问题没有历史,而是当前状态已经保存了所有会影响未来决策的信息,不再需要记录完整路径。
主示例:构造并打印状态表
下面的 Java 17 程序校验网格非空且每行长度一致,然后构造完整状态表。打印状态表可以同时验证初始化、转移和最终答案位置。
import java.util.Arrays;
public class DynamicProgrammingStateDemo {
public static void main(String[] args) {
int[][] cost = {
{1, 3, 1},
{1, 5, 1},
{4, 2, 1}
};
int[][] dp = buildMinPathSumTable(cost);
System.out.println(
"最小路径和: " + dp[cost.length - 1][cost[0].length - 1]
);
System.out.println("DP 表:");
for (int[] row : dp) {
System.out.println(Arrays.toString(row));
}
}
private static int[][] buildMinPathSumTable(int[][] cost) {
if (cost == null || cost.length == 0 || cost[0].length == 0) {
throw new IllegalArgumentException("网格不能为空");
}
int rows = cost.length;
int columns = cost[0].length;
for (int[] row : cost) {
if (row == null || row.length != columns) {
throw new IllegalArgumentException("网格每行长度必须一致");
}
}
int[][] dp = new int[rows][columns];
dp[0][0] = cost[0][0];
for (int column = 1; column < columns; column++) {
dp[0][column] = dp[0][column - 1] + cost[0][column];
}
for (int row = 1; row < rows; row++) {
dp[row][0] = dp[row - 1][0] + cost[row][0];
}
for (int row = 1; row < rows; row++) {
for (int column = 1; column < columns; column++) {
dp[row][column] = Math.min(
dp[row - 1][column],
dp[row][column - 1]
) + cost[row][column];
}
}
return dp;
}
}预期输出:
最小路径和: 7
DP 表:
[1, 4, 5]
[2, 7, 6]
[6, 8, 7]右下角 dp[2][2] = 7 表示从左上角到右下角的最小路径和为 7。状态表中的每个值都应能按定义解释,而不是只检查最终数字。
边界与复杂度
对 m × n 网格,时间复杂度为 O(mn),完整状态表空间复杂度为 O(mn)。由于每个状态只依赖上一行和当前行左侧,后续可以压缩到 O(n) 空间,但压缩前应先确认状态定义和遍历顺序正确。
常见错误包括:第一行或第一列未初始化,导致默认值 0 形成不存在的低代价路径;从右下向左上遍历却仍读取上方和左方状态;或者返回整张表的最小值,而不是定义指定的右下角状态。