64 最小路径和

给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

二、题解

思路：

1. 状态定义： 令 grid[i][j] 表示从左上角 $(0, 0)$ 走到当前位置 $(i, j)$ 的最小路径和。
2. 状态转移方程： 到达 $(i, j)$ 的最小路径和，等于到达它上方相邻节点和左方相邻节点路径和的较小值，加上它本身的值： $grid[i][j] = \min(grid[i-1][j], grid[i][j-1]) + grid[i][j]$
3. 边界处理（初始化）：
   • 起点： grid[0][0] 保持不变。
   • 第一行： 只能从左边一直走过来，因此每一格的最小路径和就是它左边那格的路径和加上自身的值：grid[0][j] += grid[0][j-1]。
   • 第一列： 只能从上面一直走下来，因此每一格的最小路径和就是它上面那格的路径和加上自身的值：grid[i][0] += grid[i-1][0]。

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;

        // 1. 初始化第一列（只能从上往下走）
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }

        // 2. 初始化第一行（只能从左往右走）
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }

        // 3. 动态规划推导其余各个位置的最小路径和
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 取左边和上边的较小值，加上当前格子的值
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }

        // 4. 右下角的值即为全局最小路径和
        return grid[m - 1][n - 1];
    }
}

合并版：

class Solution {
    public int minPathSum(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(i == 0 && j == 0) continue;
                else if(i == 0)  grid[i][j] = grid[i][j - 1] + grid[i][j];
                else if(j == 0)  grid[i][j] = grid[i - 1][j] + grid[i][j];
                else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

时间复杂度：$O(m \times n)$

空间复杂度：$O(1)$