This is a fibonacci sequence starting with 1,2 instead of 1,1. See Pattern below:

n_Value Solution

<=0 0

1 -> 1

2 -> 2

3 -> 3

4 -> 5

5 -> 8

6 -> 13

We see above that the number of steps at any ith step is basically the sum of the solution for the previous two steps. This is the main part of the solution. I have maintained an int array to store solutions at every step, so that it doesn't have to be calculated time and again.

Main observation: *steps[i] = steps[i-1] + steps[i-2]*

```
public static int climbStairs(int n) {
// Base cases
if(n <= 0) { return 0;}
if(n == 1) { return 1;}
if(n == 2) { return 2;}
int[] steps = new int[n+1];
steps[0] = 0;
steps[1] = 1;
steps[2] = 2;
for(int i=3; i<= n; i++) {
steps[i] = steps[i-1] + steps[i-2];
}
return steps[n];
}
```