# Most straight forward solution using Memoization

• 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!

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