剑指offer——跳台阶扩展问题

181 阅读 0 评论 120 点赞

我是靠谱客的博主清脆钢笔，这篇文章主要介绍剑指offer——跳台阶扩展问题，现在分享给大家，希望可以做个参考。

题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
示例1
输入
3
返回值
4

假设跳 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)

function jumpFloorII(number)
{
// write code here
return Math.pow(2,number-1)
}

以上就是清脆钢笔最近收集整理的关于剑指offer——跳台阶扩展问题的全部内容，更多相关剑指offer——跳台阶扩展问题内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。