[64] 最小路径和

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

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

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]

输出：7

解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]

输出：12

提示：

m == grid.length n == grid[i].length

这道题是一道计算二维数组最短路径的问题。

经过了回溯算法的我们看到路径问题，首先想到的就是直接做暴力 DFS。每一步都有两个选择，进行递归，计算以右侧或下侧节点为起始点的最小路径和，取较小值加上当前节点值，即可得到最短路径和。

递归终止条件为，当路径起点为右下角时，最短路径就是和就是自身。

function minPathSum(grid: number[][]): number {
  const rowLen = grid.length;
  const colLen = grid[0].length;

  const res = backtrack(0, 0);
  return res;

  function backtrack(row: number, col: number): number {
    // 越界，返回非法值，由于本题求最小值，因此设置为MAX_VALUE
    if (row >= rowLen || col >= colLen) return Number.MAX_VALUE;

    // 当前节点值
    const val = grid[row][col];

    // 递归终止条件，当路径起点为右下角时，最短路径就是和就是自身
    if (row === rowLen - 1 && col === colLen - 1) return val;

    // 做选择，分别求出右侧与下侧节点的最小路径和
    const sum1 = backtrack(row + 1, col);
    const sum2 = backtrack(row, col + 1);

    // 返回当前节点的最小路径和
    return Math.min(sum1, sum2) + val;
  }
}

但直接这样提交是会 TLE 的，说明题目需要我们对其中的情况进行剪枝优化。

说到回溯问题的优化，我们立刻会想到是否存在重叠子问题，因为这决定我们是否能够使用动态规划，通过空间来换时间。

经过思考，本题是存在重叠子问题的。原因是，grid[i][j] 的最小路径和的递归计算，会被进行两次计算，从上方 grid[i-1][j] 与左方 grid[i][j-1]。当 grid 规模较大时，这里进行递归的重复计算就会以指数级上升。

因此，我们需要将 grid[i][j] 的最小路径和缓存下来，当第二次需要获取时，不再进行递归计算，而是直接从缓存中取值返回。这样就节省了重复的递归计算，提升了时间效率。

function minPathSum(grid: number[][]): number {
  const rowLen = grid.length;
  const colLen = grid[0].length;

  const dp: number[][] = Array(rowLen)
    .fill(0)
    .map(x => Array(colLen).fill(0));

  const res = backtrack(0, 0);
  return res;

  function backtrack(row: number, col: number): number {
    // 越界，返回非法值，由于本题求最小值，因此设置为MAX_VALUE
    if (row >= rowLen || col >= colLen) return Number.MAX_VALUE;
    // 当前节点值
    const val = grid[row][col];

    // 递归终止条件，当路径起点为右下角时，最短路径就是和就是自身
    if (row === rowLen - 1 && col === colLen - 1) return val;

    // 先查memo，看是否已经计算过
    if (dp[row][col] > 0) {
      return dp[row][col];
    }

    // 做选择
    const sum1 = backtrack(row + 1, col);
    const sum2 = backtrack(row, col + 1);

    dp[row][col] = Math.min(sum1, sum2) + val;
    return dp[row][col];
  }
}

这就是动态规划最朴素的思路：处理回溯问题时，若发现重叠子问题，则将子问题的结果进行缓存，从而实现以空间换时间的优化。

这时有同学可能会发现，欸这种形态的解法用到了递归，怎么与我平时见到的动态规划的题解不太一样呢？

这是由于，我们采用的是回溯法的思路，自顶向下的解决问题。由于当前问题的解依赖了子问题的解，自然需要用到递归，这样也比较符合人类的思维模式。

而如果使用自底向上的思想呢？即先从最小情况开始求解，一步一步倒着计算回来。我们再来看看这个问题。

已知，当路径起点为右下角时，最短路径就是和就是自身。其余情况下，该点的最小路径和为其右侧与下侧节点的最短路径和的较小值加上当前值。

最后推导得出（0, 0）,即起始点的最小路径和，并返回。

function minPathSum(grid: number[][]): number {
  const rowLen = grid.length;
  const colLen = grid[0].length;

  const dp: number[] = Array(rowLen)
    .fill(0)
    .map(x => Array(colLen).fill(0));

  for (let i = rowLen - 1; i >= 0; i--) {
    for (let j = colLen - 1; j >= 0; j--) {
      // base case, 当路径起点为右下角时，最短路径就是和就是自身
      if (i + 1 === rowLen && j + 1 === colLen) {
        dp[i][j] = grid[rowLen - 1][colLen - 1];
        continue;
      }
      // 指针越界，越界值无效
      const pathSum1 = i + 1 === rowLen ? Number.MAX_VALUE : dp[i + 1][j];
      const pathSum2 = j + 1 === colLen ? Number.MAX_VALUE : dp[i][j + 1];

      dp[i][j] = Math.min(pathSum1, pathSum2) + grid[i][j];
    }
  }
  return dp[0][0];
}

这样，看着是不是就有平常的动态规划的题解形式那味儿了呢？