LC64. 最小路径和

题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。

题目解析

好的，没问题！我是 AlgoMooc 的算法老师。我们这就开始，用最通俗的方式，把这道题讲得明明白白。

---

题目在说什么

想象一下，你有一个 m 行 n 列的方格棋盘，就像下面这样：

[1, 3, 1]
[1, 5, 1]
[4, 2, 1]

每个小格子里都放着一个非负整数，代表经过这个格子需要付出的“代价”或“体力值”。

你的任务是从左上角（第0行第0列）出发，走到右下角（第 m-1 行第 n-1 列）。但是，你有一个严格的规则：每次只能向下或者向右移动一步，不能向左、向上或者斜着走。

你需要找出一条路径，使得这条路径上所有格子里的数字加起来，总和最小。这个最小的总和，就是我们要的答案。

比如上面这个例子，最短路径是 1 -> 3 -> 1 -> 1 -> 1，总和是 1+3+1+1+1 = 7。

---

思路是怎么来的

这个问题，我们怎么想到用“动态规划”来解决呢？别急，我们用生活化的比喻来理解。

1. 从“小问题”开始想

假设我们想知道从左上角走到右下角的最小路径和。这个问题很大，很复杂。但是，我们可以把它拆成小问题。

比如，我们想知道走到格子 (i, j) 的最小路径和。因为只能向右或向下走，所以走到 (i, j) 之前，我们一定是在它的左边 (i, j-1) 或者上边 (i-1, j)。

这就好比，你要去一个十字路口 (i, j)，你只能从左边那条路或者上边那条路过来。所以，到达这个路口的最小“体力消耗”，就等于“到达左边路口的最小体力消耗”和“到达上边路口的最小体力消耗”中，选一个更小的，然后再加上这个路口本身的体力消耗。

2. 用“记事本”来记录

我们不想每次都重新计算到达每个格子的最小体力，那样太慢了。所以，我们准备一个一模一样的空棋盘，叫做 dp 棋盘。dp[i][j] 就记录着从左上角走到 (i, j) 这个格子的最小体力消耗。

3. 先填好“边界”

• 第一行：因为只能向右走，所以第一行的格子，只能从左边过来。比如 dp[0][1] 就等于 dp[0][0] + grid[0][1]。就像你沿着一条直线走，只能一直往右，不能往上或往下。
• 第一列：因为只能向下走，所以第一列的格子，只能从上边过来。比如 dp[1][0] 就等于 dp[0][0] + grid[1][0]。就像你沿着一条直线走，只能一直往下，不能往左或往右。

4. 填满整个“记事本”

有了第一行和第一列，我们就可以开始填中间的部分了。对于任何一个格子 (i, j)（不是第一行也不是第一列），我们只需要看它的左边 (i, j-1) 和上边 (i-1, j) 哪个更小，然后加上它自己的值，就是到达它的最小体力。

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

这个公式就是整个问题的核心，我们把它叫做状态转移方程。

5. 找到答案

当我们把整个 dp 棋盘填满后，右下角那个格子 dp[m-1][n-1] 的值，就是我们要的答案。

---

代码逐步拆解

现在，我们对照着代码，一步一步看它是怎么实现这个思路的。

class Solution {
    public int minPathSum(int[][] grid) {

        // 1. 获取棋盘的大小
        int m = grid.length;    // 行数
        int n = grid[0].length; // 列数

        // 2. 创建一个“记事本”dp，大小和grid一样
        int[][] dp = new int[m][n];

        // 3. 初始化起点
        dp[0][0] = grid[0][0]; // 起点的最小体力就是它自己

        // 4. 填充第一行
        // 从第1列开始，到最后一列
        for(int i = 1; i < n ; i++){
            // 当前位置的最小体力 = 左边格子的最小体力 + 当前格子本身的体力
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }

        // 5. 填充第一列
        // 从第1行开始，到最后一行
        for(int i = 1; i < m ;i++){
            // 当前位置的最小体力 = 上边格子的最小体力 + 当前格子本身的体力
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }

        // 6. 填充剩下的所有格子
        // 从第1行开始，到最后一行
        for(int i = 1 ; i < m;i++){
            // 从第1列开始，到最后一列
            for(int j = 1;j < n;j++){
                // 核心公式：取左边和上边中较小的，加上当前格子本身的体力