0%

CodingInterview-变态跳台阶

这道题和上一道题思路也类似,不过递推公式变成了f(n)=f(n-1)+f(n-2)+...+f(2)+f(1)+1

解法如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int jumpFloorII(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+1;
first=first+second;
second=third;
}
return second;
}
};

因为累计的量不同,这里的 first、second 和 third 的含义发生了变化,迭代变成了当前值和之前值的累计和的加法。

经过观察,上述递推公式还可以转换成更简洁的形式:f(n)=2^(n-1)

所以代码可变为:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int jumpFloorII(int number) {
if(number<=0) return 0;
int n=1;
for(int i=1;i<number;i++){
n*=2;
}
return n;
}
};