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)$