最小路径和：压缩二维动态规划

核心结论#

到达任意单元格只可能来自上方或左侧，因此当前最小路径和等于当前权重加上两个前置状态的较小值。一维数组可以复用上一行和当前行已经计算的结果。

状态推导#

二维写法中的状态是：

dp[row][column] = grid[row][column]
  + min(dp[row - 1][column], dp[row][column - 1])

压缩到一维后，更新前的 dp[column] 代表上方，dp[column - 1] 代表左侧。第一行只能从左侧到达，第一列只能从上方到达，需要单独处理。

Java 实现#

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

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

        for (int row = 1; row < rows; row++) {
            dp[0] += grid[row][0];
            for (int column = 1; column < columns; column++) {
                dp[column] = Math.min(dp[column], dp[column - 1])
                    + grid[row][column];
            }
        }
        return dp[columns - 1];
    }
}

正确性与复杂度#

网格中的移动方向没有环，每个状态只依赖已经确定的上方和左侧状态。按从上到下、从左到右的顺序更新，就能得到所有起点到当前格的最小路径和。

• 时间复杂度：O(mn)。
• 空间复杂度：O(n)，其中 n 是列数。

验证#

覆盖单行、单列、单元素、存在零权重，以及局部最小选择并不构成全局最优的网格。

参考#

• LeetCode 64：最小路径和