最小路径和

LeetCode 官方题目链接

题目描述

给定一个包含非负整数的 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

思路拆解

这也是一道经典的二维动态规划题目，与「不同路径」非常相似。

动态规划

1. 定义状态：dp[i][j] 表示从左上角 (0, 0) 到达 (i, j) 的最小路径和。
2. 状态转移方程：
   • 到达 (i, j) 只有两种可能：从上方 (i-1, j) 或左方 (i, j-1) 过来。
   • 我们应该选择路径和较小的那一个。
   • dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
3. 初始条件：
   • dp[0][0] = grid[0][0]。
   • 第一行 dp[0][j]：只能从左边走过来，dp[0][j] = dp[0][j-1] + grid[0][j]。
   • 第一列 dp[i][0]：只能从上边走过来，dp[i][0] = dp[i-1][0] + grid[i][0]。
4. 返回值：
   • dp[m-1][n-1]。

空间优化

• 同样可以只使用一维数组。
• dp[j] 表示当前行第 j 列的最小路径和。
• 更新时：
  • 如果是第一列（j=0），只能从上方下来：dp[0] += grid[i][0]。
  • 其他列：dp[j] = Math.min(dp[j], dp[j-1]) + grid[i][j]（dp[j] 是上方的，dp[j-1] 是左边的）。

代码实现

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    // 空间优化：只使用一维数组，长度为 n
    const dp = new Array(n).fill(0);

    // 初始化第一行
    dp[0] = grid[0][0];
    for (let j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }

    // 从第二行开始遍历
    for (let i = 1; i < m; i++) {
        // 处理第一列：只能从上方下来
        dp[0] += grid[i][0];
        // 处理其他列
        for (let j = 1; j < n; j++) {
            dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }

    return dp[n - 1];
};

运行演示

假设 grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]：

1. 初始化第一行 dp: [1, 1+3=4, 4+1=5]。 dp = [1, 4, 5]。
2. i = 1 (第二行 [1, 5, 1]):
   • dp[0] += 1 -> 2。
   • j = 1: dp[1] = min(4, 2) + 5 = 7。
   • j = 2: dp[2] = min(5, 7) + 1 = 6。
   • dp 变为 [2, 7, 6]。
3. i = 2 (第三行 [4, 2, 1]):
   • dp[0] += 4 -> 6。
   • j = 1: dp[1] = min(7, 6) + 2 = 8。
   • j = 2: dp[2] = min(6, 8) + 1 = 7。
   • dp 变为 [6, 8, 7]。

返回 7。

复杂度分析

• 时间复杂度：$O(m \times n)$，需要遍历整个网格。
• 空间复杂度：$O(n)$，使用了一维数组进行优化。