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. 代码

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

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
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`)