2022-09-17算法00
请注意,本文编写于 617 天前,最后修改于 617 天前,其中某些信息可能已经过时。

斐波那契数列

相关信息

动态规划背后的基本思想非常简单。就是将一个问题拆分为子问题,一般来说这些子问题都是非常相似的,那么我们可以通过只解决一次每个子问题来达到减少计算量的目的。

一旦得出每个子问题的解,就存储该结果以便下次使用。

斐波那契数列就是从 0 和 1 开始,后面的数都是前两个数之和

0,1,1,2,3,5,8,13,21,34,55,89....

那么显然易见,我们可以通过递归的方式来完成求解斐波那契数列

function fib(n) {
  if (n < 2 && n >= 0) return n
  return fib(n - 1) + fib(n - 2)
}
fib(10)

以上代码已经可以完美的解决问题。但是以上解法却存在很严重的性能问题,当 n 越大的时候,需要的时间是指数增长的,这时候就可以通过动态规划来解决这个问题。

动态规划的本质其实就是两点

  1. 自底向上分解子问题
  2. 通过变量存储已经计算过的解

根据上面两点,我们的斐波那契数列的动态规划思路也就出来了

  1. 斐波那契数列从 0 和 1 开始,那么这就是这个子问题的最底层
  2. 通过数组来存储每一位所对应的斐波那契数列的值
function fib(n) {
  let array = new Array(n + 1).fill(null)
  array[0] = 0
  array[1] = 1
  for (let i = 2; i <= n; i++) {
    array[i] = array[i - 1] + array[i - 2]
  }
  return array[n]
}
fib(10)

本文作者:毛超颖

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!