面试高频手撕代码题

斐波那契数列（递归，DP，循环）

• 递归

时间复杂度 O(2^N) 空间复杂度 O(1)

function fiber(n) {
  if (n == 0 || n == 1) {
    return n;
  } else {
    return fiber(n - 1) + fiber(n - 2);
  }
}

console.log(fiber(5));

• DP 动态规划

时间复杂度 O(N) 空间复杂度 O(N)

function fiber(n) {
  if (n === 0 || n === 1) return n;
  var dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

• 循环

时间复杂夫 O(N) 空间复杂度 O(1)

function fiber(n) {
  if (n === 0 || n === 1) return n;
  var ret = 1;
  var a = 0;
  var b = 1;
  for (let i = 2; i < n; i++) {
    a = b;
    b = ret;
    ret = a + b;
  }
  return ret;
}