斐波拉契数列计算之从递归到记忆到动态规划的演进

递归版本：

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

这样做的问题在哪呢？ 简单粗暴的实验就是将fib(100)丢去执行基本就卡在那算不出来了，实际我们以fib(4)为例，看看是怎么计算的：

fib(2)被计算了2次，fib(1)被计算了4次，当计算规模变大时，重复的计算会越来越多，如果我们能将计算过得结果保留下来，下次直接使用，可以节省不少计算时间。

记忆递归版本：

function fib(n, arr = [1, 1]) {
  if (n <= 1) return 1;
  // 如果结果已经被保存则直接返回
  if (arr[n]) return arr[n];
  // 新增保存记录，并返回
  return (arr[n] = fib(n - 1, arr) + fib(n - 2, arr));
}

记忆优化去递归版本（时间O(n) 空间O(n)的动态规划）：

function fib(n) {
  if (n <= 1) return 1;
  let arr = [1, 1];
  for (let i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[n];
}

继续优化（时间O(n)空间O(1)的动态规划）：

function fib(n) {
  if (n <= 1) return 1;
  let [a, b] = [1, 1];
  for (let i = 2; i <= n; i++) {
    [b, a] = [a + b, b];
  }
  return b;
}

当然，这是最简单的动态规划应用，后续继续学习背包问题、最长上升子序列、最短路径等问题。