Real Dynamic Programing Solution in 0ms (NOT Fibonacci)


  • 0
    U

    public class Solution {

    int max;
    int end;
    int[] climbT;
    int[] climbF;
    
    public int climbStairs(int n) {
        if(n < 3) return n;
        this.max = 0;
        this.end = n - 1;
        climbT = new int[n - 1];
        climbF = new int[n - 1];
        for(int p = 0; p < n - 1; p++){
            climbT[p] = -1;
            climbF[p] = -1;
        }
        return maxStep(end - 1, true) + maxStep(end - 1, false);
    }
    
    private int maxStep(int i, boolean isClimb){ 
        if(i == 1){
            if(isClimb){
                if(climbT[i] == -1) climbT[i] = 2;
                return 2;
            }
            else{
                if(climbF[i] == -1) climbF[i] = 1;
                return 1;
            }
        }
        if(isClimb){
            if(climbT[i] == -1){
                max = maxStep(i - 1, true) + maxStep(i - 1, false);
                climbT[i] = max;
            }
            else return climbT[i];
        }
        else{
            if(climbF[i] == -1){
                max = maxStep(i - 1, true);
                climbF[i] = max;
            }
            else return climbF[i];
        }
        return max;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.