【JavaScript题解】【剑指offer】【变态跳台阶】

题目描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级……它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

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

解法 1: 公式推导

假设跳 n 级台阶的跳法数量是 f(n)个。

那么根据题意，青蛙可能从 n-1 级直接跳上来，也可能从 n-2 级直接跳上来，依次类推：f(n) = f(n - 1) + f(n - 2) + ... + f(1)

同理：f(n - 1) = f(n - 2) + f(n - 3) + ... + f(1)

所以，将公式 1 中的f(n - 2) + f(n - 3) + ... + f(1)替换为f(n - 1)。公式 1 变为：f(n) = f(n - 1) + f(n - 1) = f(n - 1) * 2 （公式 3）

同理：f(n - 1) = f(n - 2) + f(n - 2) = f(n - 2) * 2（公式 4）

结合公式 3 和公式 4: f(n) = f(n - 2) * 2 * 2。因此可以推出：f(n) = 2^(n - 1)

代码如下：

// 原文地址：https://xxoo521.com/2019-12-27-bian-tai-tiao-tai-jie/
// ac地址：https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387

/**
 * @param {number} number
 * @return {number}
 */
function jumpFloorII(number) {
    return Math.pow(2, number - 1);
}

相关题目