递归与动态规划

递归是从问题的结果倒推，直到问题的规模缩小到寻常。

递归中可能存在这么多的重复计算，为了消除这种重复计算，一种简单的方式就是记忆化递归。即一边递归一边使用“记录表”（比如哈希表或者数组）记录我们已经计算过的情况，当下次再次碰到的时候，如果之前已经计算了，那么直接返回即可，这样就避免了重复计算。而动态规划中 DP 数组其实和这里“记录表”的作用是一样的。

动态规划是从寻常入手， 逐步扩大规模到最优子结构。

记忆化递归和动态规划没有本质不同。都是枚举状态，并根据状态直接的联系逐步推导求解。

一个人爬楼梯，每次只能爬 1 个或 2 个台阶，假设有 n 个台阶，那么这个人有多少种不同的爬楼梯方法？

由于上第 n 级台阶一定是从 n - 1 或者 n - 2 来的，因此 上第 n 级台阶的数目就是 上 n - 1 级台阶的数目加上 n - 1 级台阶的数目。

function climbStairs(n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  return climbStairs(n - 1) + climbStairs(n - 2);
}

递归算法中，红色节点重复计算

可以使用一个 hashtable 去缓存中间计算结果，从而省去不必要的计算。

那么动态规划是怎么解决这个问题呢？ 答案也是“查表”，不过区别于递归使用函数调用栈，动态规划通常使用的是 dp 数组，数组的索引通常是问题规模，值通常是递归函数的返回值。

function climbStairs(n) {
  if (n == 1) return 1;
  const dp = new Array(n);
  dp[0] = 1;
  dp[1] = 2;

  for (let i = 2; i < n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[dp.length - 1];
}

参考

https://developer.huawei.com/consumer/cn/forum/topic/0202342555502190376?fid=18