# Climbing Stairs

## Recursion

- 0 stair has 0 way
- 1 stair has 1 way
- 2 stairs have 2 ways (0->1->2, 0->2)
- 3 stairs have 3 ways (0->1->2->3, 0->2->3, 0-1->3)
- ...

stair `3`

come be jump from stair `1`

(1 ways from 0 to here) and stair `2`

(2 ways from 0 to here).

so...

```
climbStairs(n) = climbStairs(n - 1) + climbStairs(n - 2)
```

## Space-time tradeoff

put stair `i`

into cache.

### Source code *Read on Github*

```
1 public class Solution {
2 public int climbStairs(int n) {
3 // Note: The Solution object is instantiated only once and is reused by each test case.
4
5
6 int[] step = new int[Math.max(n + 1, 3)];
7
8
9 step[0] = 0;
10 step[1] = 1;
11 step[2] = 2;
12
13 for(int i = 3; i <= n; i++){
14 step[i] = step[i - 1] + step[i - 2];
15 }
16
17 return step[n];
18 }
19 }
```