剑指offer - 青蛙跳台阶 - JavaScript

题目描述: 一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

题目描述

一只青蛙一次可以跳上 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)。

// ac地址:https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
// 原文地址:https://xxoo521.com/2019-12-26-qing-wa-tiao-tai-jie/

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
    const cache = {
        0: 0n,
        1: 1n
    };
    return __jumpFloor(n + 1) % 1000000007n; // 注意下标

    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/

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×