Most straight forward solution using Memoization


  • 0
    A

    Hi guys,

    basically the idea here is at each step, I'm in a node and I branch to the left node ie i+1 and right node ie i+2.

    Note: i stands for i'th step.

    When i reaches n, then the branch returns 1. if i+1 is bigger than n then that branch is discarded.

    Just like fib(n), this recursive call repeats a lot of these expensive calls so cache results of expensive computation for future lookup.

    public class Solution {
        Map<String, Integer> stairs = new HashMap<String, Integer>();
    
        public int climbStairs(int n) {
            stairs.put(n+","+n, 1);            //This can be memoized without computation
            stairs.put((n+1)+","+n, 0);     //This can be memoized without computation
            return recursiveClimb(0, n);
        }
        
        public int recursiveClimb(int start, int end){
            if(stairs.get(start+","+end) != null) return stairs.get(start+","+end);
            int steps = recursiveClimb(start+1, end) + recursiveClimb(start+2, end);
            stairs.put(start+","+end, steps);       //Dont forget to store the result of your computation
            return steps;
        }
    }
    

    Happy hack!


Log in to reply
 

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