Reference: LeetCode

Difficulty: Easy

## Problem

You are climbing a stair case. It takes $n$ steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

**Note:** Given $n$ will be a positive integer.

**Example:**

1 | Input: 2 |

## Analysis

### Recursion

1 | __ 2 steps |

Let denote `step[i]`

as the number of ways to reach the step $i$, where $0 \leq i \leq n$. There are two ways:

- From step $i - 1$ (one step)
- From step $i - 2$ (two steps)

Therefore, `step[i]`

can be computed by the number of ways to reach step $i - 1$ and step $i - 2$. The recurrence is as follows:

`step[i]`

= `step[i - 1]`

+ `step[i - 2]`

(no need to add or multiply any constant)

Consider the base cases `step[0] = 1`

and `step[1] = 1`

. Why should they be $1$?

It is obvious for `step[1]`

since from the group $i = 0$ to the first step there is only one way. As for `step[0]`

, ask yourself how many ways you can reach the ground? $1$. No movement is counted as one way to reach the ground.

1 | public int climbStairs(int n) { |

**Time:** $O(2^N)$**Space:** $O(N)$

### DP (Top-down & Bottom-up)

Top-down:

1 | Map<Integer, Integer> map = new HashMap<>(); |

**Time:** $O(N)$**Space:** $O(N)$

Bottom-up:

1 | public int climbStairs(int n) { |

**Time:** $O(N)$**Space:** $O(N)$

Since each time we just use two previous elements, we can just use two variables to store them.

1 | public int climbStairs(int n) { |

**Time:** $O(N)$**Space:** $O(1)$