最小路径和 - LeetCode 热题 92

大家好！我是曾续缘💖

今天是《LeetCode 热题 100》系列

发车第 92 天

多维动态规划第 2 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

最小路径和

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

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

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

难度：💖💖

解题方法

为了解决这个问题，我们可以用一个二维的数组来帮助我们记录每一个格子到左上角的最低路径和。我们逐步填充这个数组，直到我们计算出右下角的格子的路径和。

解题步骤

1. 初始化: 首先，我们初始化这个二维数组，左上角的格子的路径和就是它本身的数字。同时，我们也要初始化它的左侧和上侧的格子的路径和，因为他们是到达这个格子的唯一路径。
2. 逐步填充: 接下来，我们遍历这个网格的每一行和每一列。对于除了左上角以外的每一个格子，我们计算它到左上角的路径和，这个和就是它上方格子的路径和和左侧格子的路径和中的较小值加上它本身的数字。
3. 结果输出: 当我们填充完整个二维数组后，右下角的格子的路径和就是我们要求的答案，也就是最小路径和。

Code

class Solution {
    public int minPathSum(int[][] grid) {
        // 获取网格的行数和列数
        int m = grid.length, n = grid[0].length;
        
        // 创建一个二维数组来保存每一步的计算结果
        int[][] f = new int[m][n];
        // 初始化左上角的格子的路径和
        f[0][0] = grid[0][0];
        // 初始化第一行和第一列的路径和
        for (int i = 1; i < m; i++) {
            f[i][0] = f[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            f[0][j] = f[0][j - 1] + grid[0][j];
        }
        // 逐步填充二维数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 每个格子的路径和是它上方和左侧格子的路径和中的较小值加上它本身的数字
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
            }
        }
        // 输出右下角格子的路径和，这就是最小路径和
        return f[m - 1][n - 1];
    }
}