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

class Solution {
public:
    int jumpFloorII(int number) {
        //主要C++吧，反正quiche的rust 也没读过多少源码

        //跳上n级：跳到各个级别，然后一步跳到n 
        //f[n]=sum(f[1]...f[n-1])
        //f[n-1]=sum(f[1]...f[n-2])

        //f[n]=sum(f[n-1]+f[n-1])
        //f[n]=2f[n-1]
        int cur=1;
        for(int i=2;i<=number;i++){
            //if(i=1)    
            cur=cur*2;
        }

        return cur;
    }
};

如果重来应该怎么一步到位？

拆解成众多小规模的问题。跳到n台阶=跳到 1...n-1.然后再分别跳n-1...1步

ways[n]=ways[1]+...+ways[n-1]

注意到，转移方程之中存在可以复用的地方，即跳到n-1台阶的次数等价于∑ways[1]+...+ways[n-2]

因此 ways[n]=ways[n-1]+ways[n-1]

从第一台阶开始网上迭代即可。

注意边界条件n=0的情况，不考虑