最小路径和

网格最小路径和的状态如何定义？

• 问题: 只能向右或向下移动, 求从左上到右下经过数字之和的最小值 (64);
• 状态: dp[row][col] 为到达该格的最小路径和;
• 转移: dp[row][col] = min(dp[row-1][col], dp[row][col-1]) + grid[row][col];
• 初值:
  • dp[0][0] = grid[0][0];
  • 首行只能从左边来: dp[0][col] = dp[0][col-1] + grid[0][col];
  • 首列只能从上边来: dp[row][0] = dp[row-1][0] + grid[row][0];
• 答案: dp[m-1][n-1];
• 复杂度: 时间 O(mn), 空间 O(mn);

const minPathSum = (grid) => {
  const rows = grid.length;
  const cols = grid[0].length;
  const dp = Array.from({ length: rows }, () => new Array(cols).fill(0));
  dp[0][0] = grid[0][0];
  for (let row = 1; row < rows; row++) dp[row][0] = dp[row - 1][0] + grid[row][0];
  for (let col = 1; col < cols; col++) dp[0][col] = dp[0][col - 1] + grid[0][col];
  for (let row = 1; row < rows; row++) {
    for (let col = 1; col < cols; col++) {
      dp[row][col] = Math.min(dp[row - 1][col], dp[row][col - 1]) + grid[row][col];
    }
  }
  return dp[rows - 1][cols - 1];
};

三角形最小路径和有什么不同？

• 问题: 每行长度递增, 每步只能走到下一行的相邻位置 (120);
• 下标约定: triangle[i-1][j-1] 对应 dp[i][j], 行列都从 1 开始;
• 转移: 上一行的相邻列是 dp[i-1][j-1] 和 dp[i-1][j], 故 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i-1][j-1];
• 初值: dp[1][1] = triangle[0][0], 其余填 Infinity 以避免越界列被误选;
• 答案: min(dp[n]), 不是某一个固定位置;
• 复杂度: 时间 O(n^2), 空间 O(n^2);

const minimumTotal = (triangle) => {
  const n = triangle.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(Infinity));
  dp[1][1] = triangle[0][0];
  for (let i = 2; i <= n; i++) {
    for (let j = 1; j <= i; j++) {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i - 1][j - 1];
    }
  }
  return Math.min(...dp[n]);
};

两个问题的边界处理为什么不同？

• 网格: 首行首列是合法路径, 必须按单向累加赋值;
• 三角形: 越界列不存在, 用 Infinity 屏蔽, 让 min 自动忽略;
• 共性: 边界值决定哪些状态可参与竞争, 处理错误会让非法路径进入答案;