青蛙跳台阶 - 大师兄

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