剑指offer - 青蛙跳台阶 - JavaScript

【JavaScript系列题解】【剑指offer】

题目描述

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

专注前端与算法的系列干货分享，欢迎关注(¬‿¬)：
「微信公众号：心谭博客」| xxoo521.com | GitHub

解法 1: 斐波那契数列

这题其实就是在求斐波那契数列。理解起来也很简单。假设跳到 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)。

// 原文地址：https://xxoo521.com/2019-12-26-qing-wa-tiao-tai-jie/
// ac地址：https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4

function jumpFloor(n) {
    const cache = {
        0: 0,
        1: 1
    };
    return __jumpFloor(n + 1); // 注意下标

    function __jumpFloor(n) {
        if (cache[n] !== undefined) {
            return cache[n];
        }

        cache[n] = __jumpFloor(n - 1) + __jumpFloor(n - 2);
        return cache[n];
    }
}

更多解法

关于斐波那契还有循环写法，以及备忘录模式的其他优点。具体请看：https://xxoo521.com/2019-12-25-fei-bo-na-qi/。