CODEWITHSUNDEEP
recursiondynamic-programmingmemoization
navid
navid

Reputation: 27

Climbing stairs Leetcode 70

I know about the button up approach but I am trying to solve it with memoization and using an array instead of hashmap which you can find on the internet. But, apparently using an array causes Time Limit Exceeded error on leetcode but it shouldn't and I cannot figure out what the problem is. Anyone has any opinion why my code fails to submit?

class Solution {
    
    public int climbStairs(int n) {
        if(n<3) return n;
        Integer[] dp= new Integer[n+1];
        return climbStairs(n,dp);
    }
    
    private int climbStairs(int n,Integer[]dp){
        if(n<3) return n;
        if(dp[n]!=null) return dp[n];
        
        int step1=climbStairs(n-2);
        int step2=climbStairs(n-1);
        dp[n]=step1+step2;
        return dp[n];
    }
}

Upvotes: 0

Views: 371

Answers (1)

yaggmurss
yaggmurss

Reputation: 21

You can solve this problem by using Fibonnacci Series

Here is my code that passed all test cases

public int ClimbStairs(int n) 
{
    
        //FIBONACCI SOLUTION

        // base cases
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;

        int one = 2;
        int two = 1;
        int temp = 0;

        for (int i = 2; i < n; i++)
        {
            temp = one + two;
            two = one;
            one = temp;
        }
        return temp;
    
}

Upvotes: 1

Related Questions