斐波那契数列

1，1，2，3，5，8，... 数列从第三项开始，每一项等于前两项之和，我们要求第10项是多少我们将数学问题转换成计算机编程问题：写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下： F(0)=0,F(1)=1 F(N)=F(N−1)+F(N−2), 其中 N>1 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

暴力解析

就直接暴力递归，就可以算出我们需要的答案

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

let result = fib(10)
console.log(result) // 55

这种无脑解法可以初步解决问题，如果我们要求1000项的情况呢？

首先一个问题就是这里重复递归的次数实在是太多了，比如说我要求fib(5)，如图可视，我们重复求解了多次fib(2)和fib(3)其实这是没有必要的，我们可以用一个缓存cache，来将我们求过了的fib(n)保存在缓存中，下次用到他的时候直接读取他的值就可以了，而不是再重新递归求值，

递归 + 缓存

// 首先定义一个缓存数组，用来存放求出来的Fib(k)的值 k = 2, ... , n
let cache = [];

function fib(n) {
  // 如果缓存中已经有这个值了，就直接返回，不要再递归求值了
  if (cache[n] !== undefined) {
    return cache[n];
  }

  // 两个初始值
  if (n === 0) return 0;
  if (n === 1) return 1;

  // 递归求得fib(n)
  let v = fib(n - 1) + fib(n - 2);

  // 将fib(n)保存在cache[n]的位置
  cache[n] = v;

  // 返回fib(n)
  return v;
}
console.log(fib(1000));  //4.346655768693743e+208

动态规划

我们可以创建一个dp数组，也就是我们的斐波那契数列。

function fib(n) {
  let dp = [];
  // base case
  dp[1] = dp[2] = 1;
  for (let i = 3; i <= n; i++) {
    // 状态转移方程
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
console.log(10)  // 55

加了缓存的递归以及上面的动态规划数组减少了很多重复计算，提高了效率，但是还是可以继续在空间上进行优化的，我们直接用两个变量接收后面一个计算需要的结果，这样就不需要一个数组了~

function fib(n) {
  if (n < 2) return n;

  let i = 0;
  let j = 1;
  let sum = 1;

  // 每循环一次，将i和j的值相加得到sum放在j后面，将i和j都后移一位
  for (let k = 2; k < n; k++) {
    i = j;
    j = sum;
    sum = i + j;
  }

  return sum;
}
console.log(fib(1000)); //4.346655768693743e+208