2020-07-25 BD真题 斐波那契数列3种写法

//三种方法写斐波那契
// 1. DP
var fib1 = function(n) {
    let dp = [];
  dp[0] = 1;
  dp[1] = 1;
  for(let i=2; i<n; i++){
    dp[i] = dp[i-1]+dp[i-2];
  }
  return dp[n-1];
}

// 2. 指针交替
var fib2 = function(n) {
    if(n<=2) return 1;
    let left = 1;
  let right = 1;
  let res;
  for(let i=2; i<n; i++) {
    res = left + right;
    left = right;
    right = res;
  }
  return res;
}

// 3. 递归
var fib3 = function re(n) {
    if(n<=2) return 1;
  return re(n-1) + re(n-2);
}

console.log(fib1(10));
console.log(fib2(10));
console.log(fib3(10));