# 斐波拉契数列

斐波那契数的排列是：0，1，1，2，3，5，8，13，21，34，55，89，144……。依次类推下去，你会发现，从第3项开始，它的后一个数等于前面两个数之和，在这个数列中的数字，就被称为斐波那契数

思路一：递归

时间复杂度 O(n2)

function factorial(n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  return factorial(n-2) + factorial(n-1);
}

1
2
3
4
5

思路二：递归的时间复杂度优化（去掉重复计算）

时间复杂度 O(n)，空间复杂度 O(n)

function factorial(n, map = new Map()) {
  if (n === 1) return 1;
  if (n === 2) return 2;

  if (map.get(n)) return map.get(n);

  let res = factorial(n-2) + factorial(n-1);
  map.set(n,res)

  return res;
}

1
2
3
4
5
6
7
8
9
10
11

思路三：使用循环实现

时间复杂度 O(n)，空间复杂度 O(1)

function factorial(n) {
  if (n === 1) return 1;
  if (n === 2) return 2;

  let result = 0;
  let pre1 = 1;
  let pre2 = 2;

  for (let i = 3; i <= n; i++) {
    result = pre1 + pre2;
    pre1 = pre2;
    pre2 = result;
  }

  return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

青蛙跳台、矩形覆盖和本题类似，就不重复了