斐波那契数

【题目】

【示例】

【解法】

1.普通递归

/**
 * @param {number} N
 * @return {number}
 */
var fib = function (N) {
   if (!N) {           
     return 0;     
   }
   if (N === 1 || N === 2) {
     return 1;
   } else {
     return fib(N - 1) + fib(N - 2);
   }
};

2.动态规划

/**
 * @param {number} N
 * @return {number}
 */
var fib = function (N) {
  let p1 = 0, p2 = 1, result = 0;
  if (N < 2)
    return N;
  for (let i = 2; i <= N; i++) {
    result = p1 + p2;
    [p1, p2] = [p2, result];  //同p1=p2;p2=result;ES6的解构赋值
  }
  return result;
};