变态跳台阶
变态跳台阶
http://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387
这道题和跳台阶的思想都差不多，多列举几个数就可以发现规律：
假设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;
}
}
