题解 | 跳台阶扩展问题

import java.util.*;


public class Solution {
    // 动态规划
    public int[] dp = new int[23];
    public int jumpFloorII (int number) {
        // write code here
        // 先求出动态规划方程，对于最后一级台阶，我们可以由倒数第二级台阶跳1步，也可以由倒数第三级台阶跳两步，这样就相对于将楼梯倒过来，f(n) = f(n-1) + f(n-2) + ... + f(n-n+1)+f(n-n) = f(0) + f(1) +++ f(n-1);又f(n-1) = f(n-2) +++ f(n-n)；整理得 f(n) = f(n - 1) + f(n - 1)
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i<=number;i++){
            dp[i] = 2 * dp[i - 1];
        }
        return dp[number];
    }
}