509.md

Leetcode 509. 斐波那契数

509. 斐波那契数

递归:

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
   if(n<2){
       return n;
   }

   return fib(n-1) + fib(n-2);
};

如上所示，代码简单易懂，然后却极其低效。先不说递归方式造成栈空间的极大浪费，就仅仅是时间复杂度已经是O(2ⁿ)了。

动态规划法:

var fib = function (n) {
  if (n < 2) {
    return n;
  }

  let prev2 = 0; // fib(0) = 0
  let prev1 = 1; // fib(1) = 1;
  let result = 0; // 用于保存 prev1 + prev2 的和

  // 从 fn(2) 开始计算，
  for (let i = 2; i <= n; i++) {
    result = prev1 + prev2;// fib(n) = fib(n-1) + fib(n-2)
    // prev1, prev2, result 的值往前移
    prev2 = prev1;
    prev1 = result;
  }
  return result;
};