Climbing Stairs

EASY

You are climbing a staircase. 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? Given n will be a positive integer. Consider the following example:

Example:

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

In a simple brute force approach, we can take all possible step combinations i.e. 1 and 2, at every step. At every step, we are calling the method climb for step 1 and 2, and return the sum of returned values of both methods.

climbStairs(i,n) = climbStairs((i+1), n) + climbStairs((i+2),n);

where i defines the current stair and n defines the destination stair. Following is the recursive implementation:

int destination = 0;
public int climbStairs(int n) {
  destination = n;
  return climb(0);
}

private int climb(int currentStairNo) {
  if (currentStairNo > destination) return 0;
  if (currentStairNo == destination) return 1;
  return climb(currentStairNo + 1) + climb(currentStairNo + 2);
}

Time Complexity : O(2n). The size of the recursion tree will be 2n. The recursion tree for destination stair 3.

In the previous approach, we are redundantly calculating the result for every step. Instead, we can store the result at each step in memo array and directly returning the result from the memo array whenever that function is called again. As we can see in the above figure we are calculation climb(2) = climb(3) + climb(4) two times. Following is the recursion with memoization:

int destination = 0;
int[] memo = null;
public int climbStairs(int n) {
  memo = new int[n + 1];
  destination = n;
  return climb(0);
}

private int climb(int currentStairNo) {
  if (currentStairNo > destination) return 0;
  if (currentStairNo == destination) return 1;
  if (memo[currentStairNo] > 0) return memo[currentStairNo];
  memo[currentStairNo] = climb(currentStairNo + 1) + climb(currentStairNo + 2);
  return memo[currentStairNo];
}

  • Time Complexity: O(n). Size of recursion tree can go up to n.
  • Space Complexity: O(n). The depth of the recursion tree can go up to n.

Dynamic Programming: 

As we can see this problem can be broken into subproblems, and it contains the optimal substructure property i.e. its optimal solution can be constructed efficiently from optimal solutions of its subproblems, we can use dynamic programming to solve this problem. One can reach the ith step in one of the two ways:

  1. Taking a single step from (i−1)th step.
  2. Taking a step of 2 from  (i−2)th step.

So, the total number of ways to reach ith is equal to the sum of ways of reaching (i−1)th step and ways of reaching (i−2)th step. Let dp[i] denotes the number of ways to reach on ith step:

dp[i] = dp[i-1] + dp[i-2]
public int climbStairs(int n) {
  int[] dp = new int[n + 1];
  dp[0] = 1;
  dp[1] = 2;
  for (int i = 2; i < n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n - 1];
}

Complexity Analysis :

  • Time Complexity : O(n). Single loop up to n.
  • Space Complexity : O(n)dp array of size n is used.

Categories: Dynamic Programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s