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两个变量。