动态规划-问题推导过程

我们先以一道题为例：[64] 最小路径和。

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

从回溯算法开始

经过了回溯算法洗礼的我们看到路径问题，首先想到的就是直接做暴力 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];
  }
}

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

以自底向上的思路组织代码

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

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

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

我们设 dp[i][j] 为从 (0, 0) 开始到该点的最小路径和。那么有，该点的最小路径和为其上侧 dp[i-1][j] 与左侧节点 dp[i][j-1] 的最短路径和的较小值加上当前值。

接下来我们梳理出 base case，当当路径起点为左上角时，最短路径就是和就是自身。

最后推导得出右下角的 dp 值，即起始点到终点的最小路径和，并返回。由此我们可以写出代码：

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

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

  // base case
  for (let i = 0; i <= rowLen; i++) {
    dp[i][0] = Number.MAX_VALUE;
  }
  for (let j = 0; j <= colLen; j++) {
    dp[0][j] = Number.MAX_VALUE;
  }

  for (let i = 1; i <= rowLen; i++) {
    for (let j = 1; j <= colLen; j++) {
      // base case, 当路径终点为左上角时，最短路径和就是自身
      if (i === 1 && j === 1) {
        dp[i][j] = grid[i - 1][j - 1];
        continue;
      }
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
    }
  }
  return dp[rowLen][colLen];
}

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

这里有一些特点需要说明一下，例如我们为什么要将 dp 数组维护分别扩大一格呢？这是由于 dp[i][j] 的结果依赖 dp[i-1][j] 与 dp[i][j-1]，当 i 或 j 为 0 时会造成数组越界。当然我们也可以在遍历中进行判断与跳过处理。例如在 for 循环中，我们可以这样写：

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

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

这样就可以省去处理 base case 的两次 O(N) 循环，可以让 dp 数组大小不用+1。但会让 dp 数组之间的关系看上去没那么清晰，显得复杂。因此可读性更高的办法就是提前处理好 base case。

空间压缩

这是动态规划中最常用的优化技巧，旨在判断 dp 遍历求值的过程中是否有对相对位置的固定依赖，从而确定一些空间在遍历到某位置过后就不会再被使用，可以被丢弃或覆盖。

在本题中，我们可以轻易发现，dp[i][j] 的求值仅与 dp[i-1][j] 和 dp[i][j-1] 两个变量有关，因此，我们可以仅用一个一维数组作为缓存，并在遍历过程中不断更新缓存内容，即可在不影响算法正确性的前提下优化空间复杂度。

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

  const dp: number[] = Array(colLen).fill(0);

  // base case，先初始化好第一行的情况，当路径终点为 grid[0][j] 时，只会有从左侧过来的路径这一种可能
  dp[0] = grid[0][0];
  for (let j = 1; j < colLen; j++) {
    dp[j] = dp[j - 1] + grid[0][j];
  }

  for (let i = 1; i < rowLen; i++) {
    for (let j = 0; j < colLen; j++) {
      // 数组越界，当路径终点为 grid[i][0] 时，只会有从上方下来的路径这一种可能
      if (j === 0) {
        dp[j] = dp[j] + grid[i][j];
        continue;
      }
      dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
    }
  }
  return dp[colLen - 1];
}