数据结构与算法 / 系统课时

动态规划的状态设计

动态规划的状态设计

动态规划代码是否正确,首先取决于状态是否定义清楚。本课用网格最小路径和演示完整设计过程:一句话确定状态含义,从最后一步推导转移方程,再根据依赖关系安排初始化和遍历顺序。

学习目标

  • 用完整语句定义状态含义、范围和最终答案位置
  • 从当前状态的可选前驱推导转移方程
  • 正确处理边界初始化、遍历顺序和输入约束

状态定义决定整个算法

设 cost[row][column] 是网格代价,只允许向右或向下移动。定义 dp[row][column] 为“从左上角走到当前位置的最小路径和”。这句话同时确定了二维数组的两个维度、右下角是最终答案、当前格代价必须计入,以及前驱只能来自上方和左方。

到达内部位置的最后一步只有两种可能,因此转移方程为:

text
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 程序校验网格非空且每行长度一致,然后构造完整状态表。打印状态表可以同时验证初始化、转移和最终答案位置。

java
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;
    }
}

预期输出:

text
最小路径和: 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 形成不存在的低代价路径;从右下向左上遍历却仍读取上方和左方状态;或者返回整张表的最小值,而不是定义指定的右下角状态。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

动态规划的状态设计

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通