题解 | #跳台阶扩展问题#

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 1) return 1;
        if(number == 2) return 2;
        int n1 = 1, n2 = 2;
        int rt = 0;
        int sum = n1 + n2;
        for(int i=3; i <= number; ++i){
            rt = sum + 1;
            sum = rt + sum;
        }
        return rt;
    }
};

递推分析，但用for loop 完成。

f(n) = f(n-1) + f(n-2) + ... + f(1) + 1

第N次台阶，可能从前面的N-1次上直接跳上来，还可以一次从开始直接跳上来，所以应该是前面N-1次所有只和加上1.
其中f(1)=1, f(2)=2;
for 实现中，使用n1 n2 表示第一台阶，第二台阶的方法数作为初始值；sum表示前N-1次方法数之和。