剑指offer – 青蛙跳台阶 – JavaScript

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

题目形容

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

解法 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/8c82a5b80378478f9484d87d1c5f12a4function 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/。

专注前台与算法的系列干货分享，欢迎关注(???)

image