本文共 689 字，大约阅读时间需要 2 分钟。

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 示例1 输入 1 返回值 1

示例2

输入 4 返回值 5 这题其实就是在求斐波那契数列。理解起来也很简单。假设跳到 n 级台阶有 f(n)种方法。根据题目，青蛙在跳上 n 级时有 2 种方法：

从 n - 1 级跳 1 级上来

从 n - 2 级跳 2 级上来 青蛙跳到 n- 1 级有 f(n-1)种方法，跳到 n- 2 级有 f(n-2)种方法。所以 f(n) = f(n - 1) + f(n - 2)。这就是斐波那契数列的定义式。

需要注意的是，它和斐波那契下标不是完全对应。比如跳上 2 级，有 2 种方法。所以跳上 n 级不是 f(n)，而是 f(n + 1)。

function jumpFloor(n){
       // write code here    let cache={
           0:0,        1:1    }   return __jumpFloor(n + 1); // 注意下标 n    function __jumpFloor(n) {
           if (cache[n] !== undefined) {
               return cache[n];        }         cache[n] = __jumpFloor(n - 1) + __jumpFloor(n - 2);        return cache[n];    }}

转载地址：http://eyxnz.baihongyu.com/