最小路径和：二维动态规划基础解法

核心结论#

如果每一步只能向右或向下，到达单元格 (i, j) 的最后一步只能来自上方或左侧。用 dp[i][j] 表示到达该位置的最小路径和，就能从左上角逐格计算到右下角。

问题#

给定非负整数网格，从左上角移动到右下角，每次只能向右或向下，求路径上数字之和的最小值。

输入：
1 3 1
1 5 1
4 2 1

输出：7

状态设计#

状态转移方程为：

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

第一行只能从左侧到达，第一列只能从上方到达，因此需要单独初始化。这一步可以避免在主循环里反复判断边界。

Java 实现#

class Solution {
    public int minPathSum(int[][] grid) {
        int rows = grid.length;
        int columns = grid[0].length;
        int[][] dp = new int[rows][columns];

        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1])
                    + grid[i][j];
            }
        }

        return dp[rows - 1][columns - 1];
    }
}

正确性与复杂度#

每个状态只依赖已经计算过的上方和左侧状态。两者覆盖了所有合法的最后一步，取较小值后加上当前格子代价，即得到当前位置的最优解。

• 时间复杂度：O(mn)。
• 空间复杂度：O(mn)；进一步可以压缩为一维数组 O(n)。

验证#

验证单行、单列、1 x 1 网格和常规二维网格。对于示例网格，返回值应为 7。

参考#

• LeetCode 64：最小路径和