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

import java.util.*;


public class Solution {
    /**
     * 思路：
     跳到第n个台阶的跳法=跳到第n-1个台阶的跳法+跳到第n-2个台阶的跳法+...跳到第2个台阶的跳法+跳到第1个台阶的跳法+1
     *
     *公式为 dp[n]=dp[n-1]+dp[n-2]+...dp[2]+dp[1]+1;
     *同样dp[n-1]=dp[n-2]+dp[n-3]+...+ dp[2]+dp[1]+1;
     *两公式相减得：dp[n]=dp[n-1]*2 
     * @param number int整型 
     * @return int整型
     */
    public int jumpFloorII (int number) {
        if(number<=1){
            return 1;
        }
        int [] dp=new int[number];
        dp[0]=1;
        dp[1]=2;
        for(int i=2;i<number;i++){
            dp[i]=dp[i-1]*2;
        }
        return dp[number-1];
    }
}