Sword finger offer 10- ii Frog jumping on steps (4 solutions)

Topic link

tag: Simple dynamic programming
Write it down as dp[n] Express n The jumping of steps , Arrive at n Steps can be taken from the n-2 Step up to , You can also start with n-1 Step up to , Therefore, the number of n Step scheme tree = Arrive at n-1 Number of schemes for steps + Arrive at n-2 Number of schemes for steps , namely dp[n]=dp[n-2]+dp[n-1]

solution 1：
Use dp Array

class Solution {
    
    int mod=(int)(1e9+7);
    public int numWays(int n) {
    
        if(n<=1){
    
            return 1;
        }
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
    
            dp[i]=dp[i-2]+dp[i-1];
            dp[i]%=mod;
        }
        return dp[n];
    }
}
//O(n)
//O(n)

solution 2：
Use variables instead dp Array

class Solution {
    
    int mod=(int)(1e9+7);
    public int numWays(int n) {
    
        if(n<=1){
    
            return 1;
        }
        int dp0=1;
        int dp1=1;
        int dp2=-1;
        for(int i=2;i<=n;i++){
    
            dp2=dp0+dp1;
            dp2%=mod;
            dp0=dp1;
            dp1=dp2;
        }
        return dp2;
    }
}
//O(n)
//O(1)

solution 3：

recursive + Memory search

class Solution {
    
    int mod=(int)(1e9+7);
    int[] memo;
    public int numWays(int n) {
    
        if(memo==null){
    
            memo=new int[n+1];
        }
        if(n<=1){
    
            return 1;
        }
        if(memo[n]!=0){
    
            return memo[n];
        }else{
    
            memo[n]=numWays(n-2)+numWays(n-1);
            memo[n]%=mod;
            return memo[n];
        }              
    }
}
//O(n)
//O(n)

solution 4：

Fast power , Reference resources The finger of the sword Offer 10- I. Fibonacci sequence （4 A solution ） No 4 A solution , Just modify the initial dp[0] value , In the Fibonacci series dp[0]=0, here dp[0]=1

class Solution {
    
    int mod=(int)(1e9+7);
    public int numWays(int n) {
    
        if(n<=1){
    
            return 1;
        }
        long[][] mat={
    
            {
    1,1},
            {
    1,0}
        };
        long[][] ans={
    
            {
    1},
            {
    1}
        };
        int x=n-1;
        // Fast power algorithm 
        while(x!=0){
    
            if(x%2==1){
    
                ans=multi(mat,ans);
            }
            mat=multi(mat,mat);
            x/=2;
        }
        return (int)ans[0][0];   
    }
     // Matrix multiplication algorithm 
    public long[][] multi(long[][] a,long[][] b){
    
        //a:p*q b: q*r
        int p=a.length,q=a[0].length,r=b[0].length;
        long[][] ans=new long[p][r];
        for(int i=0;i<p;i++){
    
            for(int j=0;j<r;j++){
    
                for(int k=0;k<q;k++){
    
                    ans[i][j]+=a[i][k]*b[k][j];
                    ans[i][j]%=mod;
                }
            }
        }
        return ans;
    }
}
//O(logn)
//O(1)