剑指Offer 71：跳台阶扩展问题

链接
题目：

逆向思维，在n阶台阶上往下走，共有1+2+…n种方法；
所以f(n) = f(n−1)+f(n−2)+…+f(n−(n−1))+f(n−n) => f(0)+f(1)+f(2)+…+f(n−1)
因为f(n−1)=f(n−2)+f(n−3)+…+f((n−1)−(n−2))+f((n−1)−(n−1))；
经整理得f(n) = f(n−1)+f(n−1) = 2∗f(n−1) ，因此每级台阶方案数是前面一级台阶方案数的2倍。

import java.util.*;
public class Solution {
    int[] memo;
    public int jumpFloorII(int n) {
        memo=new int[n+1];
        Arrays.fill(memo,-1);
        return dp(n);
    }
    //
    int dp(int n){
        //base case
        if(n<=2){
            return n;
        }
        //重叠子问题
        if(memo[n]!=-1){
            return memo[n];
        }
        memo[n]=dp(n-1) * 2;
        return memo[n];
    }
}