Problem

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

OR

There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top.

Examples

Example 1:

1
2
3

Input: n = 1
Output: 1
Explanation: There is only one way to climb 1 stair

Example 2:

1
2
3
4
5

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 3:

1
2
3
4
5
6

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Example 4:

1
2
3

Input: n = 4
Output: 5
Explanation: Here are the steps - (1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2).

Solution

Method 1 - Recursion

We can easily find recursive nature in above problem.

Lets take n = 2, then we have 2 ways - either take 1 step twice or 2 steps in one go.

For n = 3, we have 3 ways:

  • One Step at a time
  • Two-step then one step
  • One step then Two-step

For n = 4, we have 5 ways: (1, 1, 1, 1), (2, 2), (1, 1, 2), (2, 1, 1), (1, 2, 1)

Now, lets take n = 6, and try to get the algorithm.

So in the next step, we need to calculate the number of ways taken to raise 5 steps and 4 steps.

We can build full tree for the steps taken as below (not complete for clarity):

Complexity

  • ⏰ Time complexity: O(2^n)
  • 🧺 Space complexity: O(n)

Code

1
2
3
4
5

int climbStairs(int n)  {
    if(n==1) return 1;
    if(n==2) return 2;
    return climbStairs(n-1)+climbStairs(n-2);
}

Method 2 - Top Down DP

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public int climbStairs(int n) {
	return climbStairs(n, new int[n + 1]);
}
private int helper(int n, int[] cache) {
	if (n == 1) {
		cache[n] = 1;
		return 1;
	}

	if (n == 2) {
		cache[n] = 2;
		return 2;
	} else if (cache[n] != 0) {
		return cache[n];
	}

	cache[n] = helper(n - 1, cache) + helper(n - 2, cache);
	
	return cache[n];
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 3 - Bottom UP DP

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int climbStairs(int n) {
	int[] dp = new int[n+1];

	//base case
	dp[1] = 1;

	if (n >= 2) {
		dp[2] = 2;
	}

	for (int i = 3; i<= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 4- Using Fibonacci Numbers

The number of ways to reach the n-th stair on a staircase depends on whether you can take one step at a time (from the (n-1)th stair) or two steps at a time (from the (n-2)th stair). We’ll represent this total number of ways to reach the n-th stair as ways(n).

1

ways(n) = ways(n-1) + ways(n-2)

This is actually formula for generating nth fibonacci number. But notice one thing that ways(n) is equal to fib(n+1), hence we can reuse fib(n) function.

1
2
3

ways(1) = fib(2) = 1
ways(2) = fib(3) = 2
ways(3) = fib(4) = 3

Code

1
2
3
4

// Returns number of ways to reach s'th stair
public int climbStairs(int s) {
	return fib(s + 1);
}

Complexity

  • ⏰ Time complexity: O(n). (It can be optimized to work in O(Logn) time using matrix approach)
  • 🧺 Space complexity: O(n)