BFE.devAI解答 - JavaScript 代码题
86. 生成 Fibonacci数

解答：

使用递归和动态规划两种方法来实现。

方法一：递归

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

时间复杂度：指数级别，约为O(2^n)。

方法二：动态规划

function fib(n) {  if(n < 2) {    return n;  }  let prev = 0;  let cur = 1;  for(let i = 2; i <= n; i++) {    let next = prev + cur;    prev = cur;    cur = next;  }  return cur;}

时间复杂度：线性，约为O(n)。

空间复杂度：常量级别，约为O(1)。因为只用到了prev、cur两个变量。