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!