Sword finger offer 71: step jumping expansion problem

link
subject ：

Ideas ： Dynamic programming

Converse thinking , stay n Go down the steps , share 1+2+…n Methods ;
therefore f(n) = f(n−1)+f(n−2)+…+f(n−(n−1))+f(n−n) => f(0)+f(1)+f(2)+…+f(n−1)
because f(n−1)=f(n−2)+f(n−3)+…+f((n−1)−(n−2))+f((n−1)−(n−1));
After sorting it out f(n) = f(n−1)+f(n−1) = 2∗f(n−1) , Therefore, the number of schemes for each step is... Of the number of schemes for the previous step 2 times .

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;
        }
        // Overlapping subproblems 
        if(memo[n]!=-1){
    
            return memo[n];
        }
        memo[n]=dp(n-1) * 2;
        return memo[n];
    }
}