动态规划算法求斐波那契数列

动态规划（Dynamic Programming）与分治方法相似，都是通过组合子问题的解来求解原问题。不同的是，分治方法通常将问题划分为互不相交的子问题，递归地求解子问题，再讲它们的解组合起来，求出原问题的解。而动态规划应用于子问题重叠的情况，即不用的子问题具有公共的子子问题。在这种情况下，如果采用分治算法，则分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题。对于动态规划法，它对每个子子问题只求解一次，将其保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。

斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：

*F*(1)=1，*F*(2)=1, *F*(n)=*F*(n - 1)+*F*(n - 2)（*n *≥ 3，*n *∈ N*）

以下是在浏览器上运行且不崩溃的几个斐波那契算法，

// 可计算十万数量级
function fibs(n){
  console.time('x')
  let fib = [0n,1n]
  for (let i = 2; i<=n; i++){
    fib[i] = fib[i-1]+fib[i-2]
  }
  console.timeEnd('x')
  return fib[n]
}

// generator函数，可计算到百万级
function fibs(n) {
  let result
  let c = (function* () {
  var a = 0n;
  var b = 1n;
  while (true) {
    yield a;
    [a, b] = [b, a + b];
  }
})()
 console.time('x')
 for(let i=0;i<=n;i++) {
   result = c.next().value
 }
 console.timeEnd('x')
 return result
}
// 
let fib = function (N) {
  let prev = 1n
  let prevPrev = 1n

  for (let i = 2; i <= N; i++) {
    let current = prev + prevPrev
    prevPrev = prev
    prev = current
  }

  return prev
};