变态跳台阶

题目描述

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

问题分析

假设跳n阶有f(n)种跳法。

若第一次跳1阶,剩下n-1阶,有f(n-1)种跳法;

若第一次跳2阶,剩下n-2阶,有f(n-2)种跳法;

若第一次跳n-1阶,剩下1阶,有f(1)种跳法;

若第一次跳n阶,有1种跳法。

则有f(n) = f(n-1) + f(n-2) + … + f(1) + 1,

f(n-1) = f(n-2) + f(n-3) + … + f(1) + 1,

f(n) = 2*f(n-1),

所以有斐波那契数列

f(n)={1if n=12f(n1)if n>1f(n) = \begin{cases} 1 &\text{if } n = 1 \\ 2*f(n-1) &\text{if } n > 1 \end{cases}

代码实现

1
2
3
4
5
6
7
8
9
public int JumpFloorII(int target) {
if (target <= 0) {
return 0;
} else if (target == 1) {
return 1;
} else {
return 2 * JumpFloorII(target - 1);
}
}

扩展思路

青蛙没遇到一个台阶,可选择跳或者不跳,除了最后一个台阶必须跳,所以有2(n1)2^{(n-1)}种跳法。

代码实现:

1
2
3
public int JumpFloorII(int target) {
return 1 << --target;
}
-------------本文结束感谢您的阅读-------------

本文标题:变态跳台阶

文章作者:huihui

发布时间:2018年10月22日 - 00:10

最后更新:2019年02月14日 - 19:02

原始链接:http://101.200.47.120:8011/2018/10/22/变态跳台阶/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。