算法 - 最小路径和

Posted on

1. 题目

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

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

示例:

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

2. 解题思路

只能向右或向下 ⇒ 到达 (i, j) 的前驱只有 (i-1, j) 和 (i, j-1)，是最经典的 DP。

2.1 状态定义

dp[i][j] = 从左上角到 (i, j) 的最小路径和。

转移方程：

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

边界：第一行只能从左边来 dp[0][j] = dp[0][j-1] + grid[0][j]；第一列只能从上边来 dp[i][0] = dp[i-1][0] + grid[i][0]。

  • 时间复杂度：O(m·n)，空间复杂度：O(m·n)。

2.2 空间优化到 O(n)

每行只依赖「上一行」和「本行左边」，可用一维滚动数组：dp[j] = grid[i][j] + min(dp[j](上一行的值), dp[j-1](本行左边的值))。

极限可原地改 grid 到 O(1)（若允许修改输入）。

3. TypeScript 实现

3.1 二维 DP（清晰）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function minPathSum(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const dp = Array.from({ length: m }, () => new Array(n).fill(0));

    dp[0][0] = grid[0][0];
    for (let j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    for (let i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m - 1][n - 1];
}

console.log(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])); // 7

3.2 一维滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function minPathSumOpt(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const dp = new Array(n).fill(0);

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i === 0 && j === 0) dp[j] = grid[0][0];
            else if (i === 0) dp[j] = dp[j - 1] + grid[i][j];       // 第一行
            else if (j === 0) dp[j] = dp[j] + grid[i][j];           // 第一列，dp[j] 仍是上一行值
            else dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }

    return dp[n - 1];
}

4. 面试延伸

  • 变体：不同路径（计数而非求和）把 min 换成 +，是同一网格 DP 骨架。
  • 带障碍 / 三角形最小路径和 / 地下城游戏：注意「地下城游戏」需从右下倒推（HP 约束），说明并非所有网格 DP 都能正向做。
  • 追问：为什么一维数组里 dp[j] 在更新前代表上一行？因为本行还没覆盖它，天然滚动——这是滚动数组的核心技巧。

难度：中等 | LeetCode 64 | 网格 DP 入门