Leetcode 最小路径和

这段代码解决的是LeetCode第64题“最小路径和”，其核心思想是动态规划（Dynamic Programming，简称DP）。以下是算法的具体解释：

1. 问题描述：

我们给定一个包含非负整数的 m x n 网格（grid），需要找出从左上角到右下角的路径，使得路径上的数字总和最小。每次只能向下或向右移动。

2. 动态规划思想：

我们用一个二维数组 dp 来记录每个位置上到达该位置的最小路径和。

• dp[i][j] 表示从起点 (0, 0) 到达位置 (i, j) 的最小路径和。
• 初始条件：左上角 dp[0][0] 就是 grid[0][0]。
• 对于每个位置 (i, j)，它的路径只能从上方或左侧走过来：
  • 如果从上方 (i-1, j) 来，那么路径和是 dp[i-1][j] + grid[i][j]；
  • 如果从左侧 (i, j-1) 来，那么路径和是 dp[i][j-1] + grid[i][j]；
  • 我们选择这两个路径中的最小值，因此 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。

3. 边界情况：

• 第一行（即 i == 0）：只能从左边来，所以 dp[0][j] = dp[0][j-1] + grid[0][j]。
• 第一列（即 j == 0）：只能从上边来，所以 dp[i][0] = dp[i-1][0] + grid[i][0]。

4. 最终结果：

最后，dp[m-1][n-1]（即右下角的值）就是我们所求的从左上角到右下角的最小路径和。

5. 算法时间复杂度和空间复杂度：

• 时间复杂度：O(m * n)，其中 m 是网格的行数，n 是列数。我们需要遍历整个 m x n 的网格，因此时间复杂度是 m * n。
• 空间复杂度：O(m * n)，我们使用了一个额外的 dp 数组来存储每个位置的最小路径和。如果优化空间复杂度，也可以在原数组 grid 上进行修改。

总的来说，这个算法通过动态规划的方式，从起点开始，逐步计算出到每个位置的最小路径和，最终得到到达终点的最小路径。

Java solution

class Solution {
    public int minPathSum(int[][] grid) {
        //dp[i][j]表示到达i,j时的最小路径和
        int[][] dp = new int [grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < grid.length; ++i) { //i从1开始
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for(int j = 1; j < grid[0].length; ++j) {//j从1开始
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

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