变态跳台阶

这道题和跳台阶的思想都差不多，多列举几个数就可以发现规律：

假设dp[i]表示跳到第i层的方法，则

这里又可以想到利用DP的思想建立一个数组保存前i项和：

于是化简可得，省区了dp数组，只保存sum和即可，代码如下：

public class Solution {
    public int JumpFloorII(int target) {
        ArrayList<Integer> sum = new ArrayList<>();
        sum.add(1);
        for(int i=1;i<target;i++){
            sum.add(sum.get(i-1)*2+1);
        }
        if(target == 1) return 1;
        return sum.get(target-2)+1;
    }
}