政子的博客

技术|学习|随笔

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;
    }
};