最小路径和 - Stellar Observer Protocol

632 字

3 分钟

最小路径和

2025-08-11

Algorithms

数组

/

动态规划

/

矩阵

题目描述#

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

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

解题思路#

动态规划核心：
- 定义 dp[i][j] 表示从左上角到 (i,j) 的最小路径和
- 初始化 dp = grid
- 状态转移方程： dp[i][j] = grid[i][j] + min( dp[i-1][j], // 从上方来 dp[i][j-1] // 从左方来 )
边界处理：
- 首行：只能从左来 dp[j] = grid[j] + dp[j-1]
- 首列：只能从上来 dp[i] = grid[i] + dp[i-1]
空间优化：
- 用滚动数组（单行存储）代替二维 DP
- 迭代更新：dp[j] = grid[i][j] + min(dp[j], dp[j-1])

关键洞察#

最优子结构：
- 当前点最小路径仅依赖上方和左方邻居
- 无后效性：后续决策不受前序路径影响
单行滚动原理：
- 计算第 i 行时只需第 i-1 行数据
- 按列从左到右更新可覆盖历史状态
原地修改可行性：
- 若允许修改输入网格，可直接在 grid 上操作
- grid[i][j] 累加上方/左方较小值
方向约束优势：
- 只能向右/向下移动简化状态转移
- 无需考虑斜向或回头路径

复杂度分析#

指标	说明
时间复杂度	O(mn)：必须遍历网格所有元素（m 行 n 列）
空间复杂度	O(n)：使用单行 DP 数组（滚动数组优化）O(1)：原地修改输入网格

代码实现#

1
/**
2
 * @link {https://leetcode.cn/problems/minimum-path-sum}
3
 * @param {number[][]} grid
4
 * @return {number}
5
 */
6
var minPathSum = function (grid) {
7
    const m = grid.length, n = grid[0].length;
8
    for (let i = 0; i < m; i++) {
9
        for (let j = 0; j < n; j++) {
10
            if (i === 0 && j === 0) continue;
11
            if (i === 0) grid[i][j] += grid[i][j - 1];
12
            else if (j === 0) grid[i][j] += grid[i - 1][j];
13
            else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
14
        }
15
    }
16
    return grid[m - 1][n - 1];
17
};