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
2
3
4
5
6
7
8
9
10
Input: 2
Output: 2
1. 1 step + 1 step
2. 2 steps

Input: 3
Output: 3
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Analysis

Recursion

1
2
3
      __ 2 steps
   __|   1 step
__|

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
2
3
4
public int climbStairs(int n) {
  if (n <= 1) return 1;
  return climbStairs(n - 1) + climbStairs(n - 2);
}

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

DP (Top-down & Bottom-up)

Top-down:

1
2
3
4
5
6
7
Map<Integer, Integer> map = new HashMap<>();
public int climbStairs(int n) {
  if (n <= 1) return 1;
  if (!map.containsKey(n - 1)) map.put(n - 1, climbStairs(n - 1));
  if (!map.containsKey(n - 2)) map.put(n - 2, climbStairs(n - 2));
  return map.get(n - 1) + map.get(n - 2);
}

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

Bottom-up:

1
2
3
4
5
6
7
8
9
public int climbStairs(int n) {
  int[] dp = new int[n + 1];
  dp[0] = 1;
  dp[1] = 1;
  for (int i = 2; i <= n; ++i) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[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
2
3
4
5
6
7
8
9
public int climbStairs(int n) {
  int s1 = 1, s2 = 1;
  for (int i = 2; i <= n; ++i) {
    int temp = s1 + s2;
    s1 = s2;
    s2 = temp;
  }
  return s2;
}

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