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

使用和跳台阶一样的思路。模拟跳的过程，将n阶台阶分为第一次跳1阶，第一次跳2阶，...，第一次跳n阶。
这样就得到了一个类似于原始跳台阶的公式，f(n)=f(1)+f(2)+...+f(n-1)+1，f(n)表示n阶台阶的跳法数。
最后不是加f(n)而是加1，是因为一次跳n个台阶就直接跳完了，只有一种跳法。如果加f(n)的话会使等式不成立，使递归无出口。这个最后加1在代码中体现为返回++sum。
由于在循环中调用递归，所以时间复杂度在O(n^2)，是比较大的，算法还有进一步优化的空间。

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 0){
            return 0;
        }
        else if(number == 1){
            return 1;
        }
        else if(number == 2){
            return 2;
        }
        int sum = 0;
        for(int i = 1;i < number;i++){
            sum += jumpFloorII(i);
        }
        return ++sum;
    }
};