Climbing stairs - TutorialCup

Table of Contents

Problem Statement

The problem “Climbing stairs” states that you are given a staircase with n stairs. At a time you can either climb one stair or two stairs. How many numbers of ways to reach the top of the staircase?

Example

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

Climbing stairs

The image shows the ways to move.

So our answer is 3.

Recursive Approach

We can observe that number of ways to reach ith stair is the summation of the number of ways to reach (i-1)the stair and number of ways to reach (i-2)th stair. So our recursive equation becomes

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

Code

C++ code for Climbing Stairs

#include <bits/stdc++.h> 
using namespace std; 

// A recursive function used by countWays 
int countWaysUtil(int n, int m) 
{ 
  if (n <= 1) 
  { 
    return n; 
  } 
  
  int res = 0; 
  for(int i = 1; i <= m && i <= n; i++) 
  { 
  res += countWaysUtil(n - i, m); 
  } 
  return res; 
} 

// Returns number of ways to reach s'th stair 
int countWays(int s, int m) 
{ 
  return countWaysUtil(s + 1, m); 
} 

// Driver code 
int main() 
{ 
  int s = 4, m = 2; 
  cout << "Nuber of ways = " << countWays(s, m); 

  return 0; 
}

Java code for Climbing Stairs

class stairs { 
  // A recursive function used by countWays 
  static int countWaysUtil(int n, int m) 
  { 
    if (n <= 1) 
      return n; 
    int res = 0; 
    for (int i = 1; i <= m && i <= n; i++) 
      res += countWaysUtil(n - i, m); 
    return res; 
  } 

  // Returns number of ways to reach s'th stair 
  static int countWays(int s, int m) 
  { 
    return countWaysUtil(s + 1, m); 
  } 

  /* Driver program to test above function */
  public static void main(String args[]) 
  { 
    int s = 4, m = 2; 
    System.out.println("Number of ways = "
            + countWays(s, m)); 
  } 
}

Complexity Analysis

Time Complexity

O(2^n), because in recursive approach for each stair we have two options: climb one stair at a time or climb two stairs at a time. As we are checking for all possible cases so for each stair we have 2 options and we have total n stairs so time complexity becomes O(2^n)

Space Complexity

O(n) because space is required by the compiler to use recursion. The recursion also requires stack and thus storing that makes this O(n) space because recursion will be almost n deep.

Dynamic Programming Approach

The recursive approach includes the recomputation of the same values again and again. For this we use memoization and when we calculate it for some input we store it in the memoization table. When we need it later we don’t compute it again and directly use its value from the table. We maintain table ways[] where ways[i] stores the number of ways to reach ith stair. So ways[n-1] is our answer.