# 1. 题目描述

一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

# 2. 思路分析

跳到 n 阶假设有 f(n)种方法。

往前倒退,如果青蛙最后一次是跳了 2 阶,那么之前有 f(n-2)种跳法; 如果最后一次跳了 1 阶,那么之前有 f(n-1)种跳法。

所以:f(n) = f(n-1) + f(n-2)。就是斐波那契数列。

# 3. 代码

这里利用缓存模式(又称备忘录模式)实现了代码。

const fibonacci = (() => {
  let mem = new Map();
  mem.set(1, 1);
  mem.set(2, 1);

  const _fibonacci = n => {
    if (n <= 0) {
      throw new Error("Unvalid param");
    }

    if (mem.has(n)) {
      return mem.get(n);
    }

    mem.set(n, _fibonacci(n - 1) + _fibonacci(n - 2));
    return mem.get(n);
  };

  return _fibonacci;
})();

/**
 * 测试代码
 */

let start = new Date().getTime(),
  end = null;

fibonacci(8000);
end = new Date().getTime();
console.log(`耗时为${end - start}ms`);

start = end;
fibonacci(8000);
end = new Date().getTime();
console.log(`耗时为${end - start}ms`);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36