CodingInterview-跳台阶

这道题是斐波那契额数列的一个延伸,本质还是一个斐波那契额数列,只是起始值不同。

首先,如果台阶的阶数为 1,那么只有一种跳法,记为 f(1),如果台阶的阶数为 2,那么就会有两种跳法(一次一阶跳两次和直接跳两阶),记为 f(2)

接着,如果阶数为 3,那么第一次如果跳了一阶,那么后面还剩两阶,即 f(2),如果第一次跳了两阶,那么后面还剩一阶,即 f(1)

如果阶数更高(n 阶),那么依旧按照这个规律,按照第一次跳的情况将后面分为两种情况:f(n-1)f(n-2),然后将这两种加起来就可以得到结果了,即 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<=0) return 0;
if(number==1) return 1;
if(number==2) return 2;
int first=1,second=2;
for(int i=3;i<=number;i++){
int third=first+second;
first=second;
second=third;
}
return second;
}
};