剑指offer - 变态跳台阶 - JavaScript

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

# 题目描述

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

# 解法 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);
}

# 相关题目

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