Fibonacci using cache

```
public class Solution {
static int[] arr = new int[35535];
public int climbStairs(int n) {
if(arr[n] != 0) return arr[n];
if(n < 3)
{
arr[n] = n;
return n;
}
int res = climbStairs(n-1) + climbStairs(n-2);
arr[n] = res;
return res;
}
}
```

Using Stack

```
public class Solution {
public int climbStairs(int n) {
if(n < 3) return n;
Stack<Integer> st = new Stack<Integer>();
st.push(new Integer(1));
st.push(new Integer(2));
int i = 3;
while(i <= n){
Integer a = st.peek();
st.pop();
Integer b = st.peek();
st.push(a);
st.push(new Integer(a.intValue() + b.intValue()));
i++;
}
return st.peek().intValue();
}
}
```