跳台阶

常见的跳台阶问题有两种,而它们的本质依旧是和斐波那契数列有关。

跳台阶

  • 题目描述:

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

  • 解题思路:

根据题意,
当n=1时,f(1)=1;
当n=2时,青蛙可以一次跳2级,也可以两次跳1级,f(2)=2
当n=3时,我们可以倒过来思考这个问题,假设青蛙已经完成了跳台阶,我们可以考虑一下它最后一步是如何跳过来的,f(3)就等于各种情况下跳台阶次数之和。
我们能够看出,这时只有两种情况:
①最后一次是跳了1级台阶,也就是从第二级台阶跳了一次完成任务
②最后一次是跳了2级台阶,也就是从第一级台阶跳了一次完成任务
所以f(3)=①+②
情况①等于青蛙跳到第二级台阶的次数
情况②等于青蛙跳到第一级台阶的次数
所以f(3)=f(2)+f(1)
依次类推,f(n)=f(n-1)+f(n-2),满足斐波那契数列特征。

  • 源代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int jumpFloor(int number) {
if (number == 1) return 1;
if (number == 2) return 2;
int f1 = 1,f2 = 2;
int f3;
for (int i=3;i<=number;i++) {
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}
};

变态跳台阶

  • 题目描述:

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

  • 解题思路:

它是对跳台阶问题的一个变形,不再限制青蛙一次可以跳台阶的级数,类比跳台阶问题的解题思路,
例如当n=5时,我们依旧可以倒过来去思考这个问题,假设青蛙已经完成了跳台阶,我们可以考虑一下它最后一步是如何跳过来的,跳台阶的总数就等于各种情况下跳台阶的次数之和。
①最后一次是跳了1级台阶,也就是从第4级台阶跳了一次完成任务
②最后一次是跳了2级台阶,也就是从第3级台阶跳了一次完成任务
③最后一次是跳了3级台阶,也就是从第2级台阶跳了一次完成任务
④最后一次是跳了4级台阶,也就是从第1级台阶跳了一次完成任务
⑤最后一次是跳了5级台阶,也就是从第0级台阶跳了一次完成任务
所以f(5)=①+②+③+④+⑤
情况①等于青蛙跳到第4级台阶的次数
情况②等于青蛙跳到第3级台阶的次数
情况③等于青蛙跳到第2级台阶的次数
情况④等于青蛙跳到第1级台阶的次数
情况⑤等于青蛙直接从起点跳到了终点
所以f(5)=f(4)+f(3)+f(2)+f(1)+1
依次类推,f(n)=f(n-1)+f(n-2)+f(n-3)+…+f(1)+1
将该规律式进行整理,f(n+1)=f(n)+f(n-1)+…+f(1)+1
两式相减,可以得到:f(n+1)=2*f(n)
找到该题的规律之后,问题便非常简单了。

  • 源代码:
1
2
3
4
5
6
7
8
class Solution {
public:
int jumpFloorII(int number) {
if (number == 1) return 1;
if (number == 2) return 2;
return 2*jumpFloorII(number-1);
}
};
-------------The End-------------