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

  • 2019-11-24
  • 0
  • 0

递归版本:

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

这样做的问题在哪呢? 简单粗暴的实验就是将fib(100)丢去执行基本就卡在那算不出来了,实际我们以fib(4)为例,看看是怎么计算的:
https://s2.ax1x.com/2019/11/24/MLFxfg.md.png
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;
}

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

上一篇:    

评论

还没有任何评论,你来说两句吧

发表评论

me@ccc5.cc - 衫小寨