最小路径和

问题

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

限制：每次只能向下或向右移动一步。

示例：

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

解答

动态规划

/**
 * 计算最小路径和
 * @param {number[][]} grid - 网格
 * @return {number} - 最小路径和
 */
function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  
  // 创建 dp 数组，dp[i][j] 表示到达 (i,j) 的最小路径和
  const dp = Array.from({ length: m }, () => 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] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
  }
  
  return dp[m - 1][n - 1];
}

// 测试
const grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
];
console.log(minPathSum(grid)); // 7

空间优化版本

/**
 * 空间优化：只用一维数组
 * @param {number[][]} grid
 * @return {number}
 */
function minPathSumOptimized(grid) {
  const m = grid.length;
  const n = grid[0].length;
  
  // 只需要一行的空间
  const dp = 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];
      } else {
        // 取左边和上边的较小值
        dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
      }
    }
  }
  
  return dp[n - 1];
}

关键点

• 状态定义：dp[i][j] 表示从起点到 (i, j) 的最小路径和
• 状态转移：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
• 边界处理：第一行只能从左来，第一列只能从上来
• 空间优化：可以用一维数组滚动更新，空间从 O(mn) 降到 O(n)
• 时间复杂度：O(mn)，需要遍历整个网格