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:

## Analysis

### Recursion

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.

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

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

Top-down:

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

Bottom-up:

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

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

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

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.