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

刚开始用记忆化动态规划来做，比较简单，但是没有发现它的规律。

过完测试用例发现，我们求的f[n] = f[n-1]+f[n-2]+f[n-3]+... +f[0]

而f[n-1]=f[n-2]+f[n-3]+...+f[0]

所以f[n]正好等于2*f[n-1]

已知f[0] = f[1] = 1

所以容易得到f[2]=2,f[3]=4,f[4]=8 由此得到规律-->f[n]=2*(n-1)【n>=1】

public class Solution {

public int jumpFloorII(int target) {
    
    //方法一 记忆动态规划
    if(target<=1)
        return 1;
    int[] dp = new int[50];
    for(int i=1;i<50;++i){
        dp[i] = 1;
    }
    for(int i=2;i<=target;++i){
        int index=1;
        while(i-index>=0){
            dp[i] += dp[i-index];
            index++;
        }
    }
    return dp[target];
    
    //方法二 找规律
    return (int)Math.pow(2,target-1);
}

}