最小路径和 - 从零开始理解二维DP

二维数组让你蒙了？没关系！我们从最简单的例子开始，一步步理解二维动态规划的思路。

🎯 问题描述

给你一个二维网格，每个格子里有一个数字，你要从左上角走到右下角，每次只能向右或向下移动一步，求路径上数字和的最小值。

📝 举个简单例子

网格：
[1, 3, 1]
[1, 5, 1] 
[4, 2, 1]

目标：从 (0,0) 走到 (2,2)，找最小路径和

🤔 先用人脑思考

第一步：画出所有可能的路径

起点(0,0) → 终点(2,2)

路径1: 1 → 3 → 1 → 1 → 1 = 7
       ↓   ↓   →   →   
路径2: 1 → 3 → 5 → 1 → 1 = 11  
       ↓   →   ↓   →
路径3: 1 → 1 → 5 → 1 → 1 = 9
       →   ↓   ↓   →
路径4: 1 → 1 → 4 → 2 → 1 = 9
       →   →   ↓   ↓
路径5: 1 → 1 → 1 → 2 → 1 = 6  ← 最小！
       →   →   →   ↓
路径6: 1 → 1 → 1 → 5 → 1 = 9
       →   →   ↓   ↓

答案是6，但这样枚举太累了！能不能更聪明一点？

💡 动态规划的核心思想

关键洞察：

到达任意一个格子的最小路径和 = 该格子的值 + 到达该格子前一步的最小路径和

因为只能向右或向下移动，所以到达格子(i,j)只有两种可能：

从上面(i-1,j)向下走来
从左边(i,j-1)向右走来

选择这两种方式中路径和更小的那个！

🔍 一步步分析过程

第一步：理解状态定义

// dp[i][j] 表示：从起点(0,0)到达位置(i,j)的最小路径和

第二步：手工计算每个位置

让我们用一个表格来记录每个位置的最小路径和：

原始网格：
[1, 3, 1]
[1, 5, 1]
[4, 2, 1]

DP表格（一步步填充）：
[?, ?, ?]
[?, ?, ?]
[?, ?, ?]

🚀 开始填充：

1. 起点 (0,0)

dp[0][0] = 1  // 起点就是网格[0][0]的值

[1, ?, ?]
[?, ?, ?]
[?, ?, ?]

2. 第一行（只能向右走）

dp[0][1] = dp[0][0] + grid[0][1] = 1 + 3 = 4
dp[0][2] = dp[0][1] + grid[0][2] = 4 + 1 = 5

[1, 4, 5]
[?, ?, ?]
[?, ?, ?]

3. 第一列（只能向下走）

dp[1][0] = dp[0][0] + grid[1][0] = 1 + 1 = 2
dp[2][0] = dp[1][0] + grid[2][0] = 2 + 4 = 6

[1, 4, 5]
[2, ?, ?]
[6, ?, ?]

4. 其他位置（可以从上面或左边来）

位置 (1,1)：

从上面来：dp[0][1] + grid[1][1] = 4 + 5 = 9
从左边来：dp[1][0] + grid[1][1] = 2 + 5 = 7
选择更小的：dp[1][1] = min(9, 7) = 7

[1, 4, 5]
[2, 7, ?]
[6, ?, ?]

位置 (1,2)：

从上面来：dp[0][2] + grid[1][2] = 5 + 1 = 6
从左边来：dp[1][1] + grid[1][2] = 7 + 1 = 8
选择更小的：dp[1][2] = min(6, 8) = 6

[1, 4, 5]
[2, 7, 6]
[6, ?, ?]

位置 (2,1)：

从上面来：dp[1][1] + grid[2][1] = 7 + 2 = 9
从左边来：dp[2][0] + grid[2][1] = 6 + 2 = 8
选择更小的：dp[2][1] = min(9, 8) = 8

[1, 4, 5]
[2, 7, 6]
[6, 8, ?]

位置 (2,2)：

从上面来：dp[1][2] + grid[2][2] = 6 + 1 = 7
从左边来：dp[2][1] + grid[2][2] = 8 + 1 = 9
选择更小的：dp[2][2] = min(7, 9) = 7

[1, 4, 5]
[2, 7, 6]
[6, 8, 7]

最终答案：dp[2][2] = 7

💻 代码实现（超详细注释）

function minPathSum(grid) {
  const m = grid.length;    // 行数
  const n = grid[0].length; // 列数
  
  // 创建DP表格，dp[i][j]表示到达(i,j)的最小路径和
  const dp = Array(m).fill().map(() => Array(n).fill(0));
  
  // 第1步：设置起点
  dp[0][0] = grid[0][0];
  console.log('起点:', dp[0][0]);
  
  // 第2步：填充第一行（只能向右走）
  for (let j = 1; j < n; j++) {
    dp[0][j] = dp[0][j - 1] + grid[0][j];
    console.log(`第一行 (0,${j}):`, dp[0][j]);
  }
  
  // 第3步：填充第一列（只能向下走）
  for (let i = 1; i < m; i++) {
    dp[i][0] = dp[i - 1][0] + grid[i][0];
    console.log(`第一列 (${i},0):`, dp[i][0]);
  }
  
  // 第4步：填充其他位置（从上面或左边来，选择更小的）
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      const fromTop = dp[i - 1][j] + grid[i][j];    // 从上面来
      const fromLeft = dp[i][j - 1] + grid[i][j];   // 从左边来
      
      dp[i][j] = Math.min(fromTop, fromLeft);       // 选择更小的
      
      console.log(`位置 (${i},${j}): 从上=${fromTop}, 从左=${fromLeft}, 选择=${dp[i][j]}`);
    }
  }
  
  // 打印最终的DP表格
  console.log('最终DP表格:');
  dp.forEach((row, i) => {
    console.log(`第${i}行:`, row);
  });
  
  return dp[m - 1][n - 1]; // 返回右下角的值
}

// 测试
const grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
];

console.log('网格:');
grid.forEach((row, i) => {
  console.log(`第${i}行:`, row);
});

console.log('\n开始计算...\n');
const result = minPathSum(grid);
console.log('\n最小路径和:', result);

🎨 可视化理解

用箭头表示最优路径：

原始网格:        DP表格:         最优路径:
[1, 3, 1]       [1, 4, 5]       [→, →, ↓]
[1, 5, 1]   →   [2, 7, 6]   →   [?, ?, →]  
[4, 2, 1]       [6, 8, 7]       [?, ?, ✓]

最优路径：(0,0) → (0,1) → (0,2) → (1,2) → (2,2)
路径和：1 + 3 + 1 + 1 + 1 = 7

🧠 理解要点

1. 为什么用二维数组？

因为问题本身就是二维的（网格）
每个位置的最优解都需要保存
后面的计算需要用到前面的结果

2. 状态转移方程

dp[i][j] = Math.min(
  dp[i-1][j] + grid[i][j],  // 从上面来
  dp[i][j-1] + grid[i][j]   // 从左边来
)

3. 边界条件

第一行：只能从左边来
第一列：只能从上面来
起点：就是原始值

4. 计算顺序

必须从左上角开始
按行或按列依次计算
保证计算当前位置时，依赖的位置已经算好了

🚀 空间优化版本

理解了基本思路后，我们可以优化空间复杂度：

function minPathSumOptimized(grid) {
  const m = grid.length;
  const n = grid[0].length;
  
  // 只需要一行的空间！
  const dp = [...grid[0]]; // 复制第一行
  
  console.log('初始化第一行:', dp);
  
  // 逐行更新
  for (let i = 1; i < m; i++) {
    // 更新第一列
    dp[0] += grid[i][0];
    console.log(`第${i}行开始，第一列更新为:`, dp[0]);
    
    // 更新其他列
    for (let j = 1; j < n; j++) {
      // dp[j] 是从上面来的值（上一行的结果）
      // dp[j-1] 是从左边来的值（当前行已更新的结果）
      dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
      console.log(`  位置(${i},${j})更新为:`, dp[j]);
    }
    
    console.log(`第${i}行完成:`, [...dp]);
  }
  
  return dp[n - 1];
}

// 测试优化版本
console.log('\n=== 空间优化版本 ===');
const result2 = minPathSumOptimized(grid);
console.log('最小路径和:', result2);

🎯 练习建议

1. 手工计算

先用纸笔手工计算几个小例子，理解每一步的逻辑。

2. 修改例子

试试不同的网格，看看结果如何变化：

// 简单例子
const grid1 = [
  [1, 2],
  [3, 4]
];

// 复杂例子  
const grid2 = [
  [1, 4, 8, 6, 2],
  [2, 7, 3, 8, 4],
  [8, 4, 2, 6, 5]
];

3. 调试技巧

打印每一步的计算过程
画出DP表格的填充过程
验证边界条件的处理

🔗 相关问题

掌握了最小路径和，你就能解决这些类似问题：

不同路径：计算有多少种走法
不同路径II：有障碍物的情况
最大路径和：求最大值而不是最小值
三角形最小路径和：三角形形状的网格

💡 总结

二维DP的核心思路：

状态定义：dp[i][j] 表示到达位置(i,j)的最优解
状态转移：当前位置的最优解 = 当前值 + 前面位置的最优解
边界处理：第一行、第一列需要特殊处理
计算顺序：从左上角开始，逐行或逐列计算

记住这个模板，所有二维DP问题都是这个套路！

下次遇到二维DP，不要慌！先画个小例子，手工算一遍，理解了思路再写代码。 🎉