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

第四十四题 前面的跳台阶动态规划的加深 可能跳不定的台阶 需要维护一个sum

class Solution {
public:
    int jumpFloorII(int number) {
        // 相比正常跳 每次多一种直接跳出去
        // 假如说 number是4  那么 结果就等于3的全部可能性（4跳了一步到3）+2的全部可能性(4跳到2）+1的全部可能性（4跳到1）+1(4直接跳出去)
        // 而前面每次321的全部可能都是数组求和，所以可以弄一个sum 一直用来累加
        int *a = new int[number];
        if(number==1) return 1;
        if(number==2) return 2;
        a[0]=1;
        int sum=1;
        // 可以只用sum 循环 最后返回sum
        // 这里放到数组里 只是为了解释清楚 到底前面每一项是怎么出来的
        for(int i =1;i<number;i++)
        {
            a[i]=sum+1;
            sum+=a[i];
        }
//         for(int i =0;i<number;i++)
//         {
//             cout<<a[i]<<endl;
//         }
        // 这边输出了结果发现，答案是2^(number-1) 思考一下为啥
        // return pow(2,number-1);
        // 提示：
        // 假设是3 = 1+2+1 =4 sum=1+2+4=7
        // 假设是4 = 1+2+4+1=8 sum=1+2+4+8=15
        // 假设是5 = 1+2+4+8+1=16 sum+1+2+4+8+16=31
        
        // 所以ans=sum+1 而sum=sum+ans=2*sum+1 每次翻一倍+1 再到下一次输出ans再+1，正好就成了每次翻倍
        return a[number-1];
    }
};