Climbing stairs

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Expedia Goldman Sachs
Dynamic ProgrammingViews 1666

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

3
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

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; 
}
5

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)); 
  } 
}
5

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.

Code

C++ code for Climbing Stairs

#include <stdio.h> 

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

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

// Driver program to test above functions 
int main() 
{ 
  int s = 4, m = 2; 
  printf("Number of ways = %d", countWays(s, m)); 
  return 0; 
} 
5

Java code for Climbing Stairs

// Java program to count number of ways 
// to reach n't stair when a person 
// can climb 1, 2, ..m stairs at a time 

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

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

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

Complexity Analysis

Time Complexity

O(m*n) here m is the number of ways which is 2 for this problem and n is the number of stairs.

Space Complexity

O(n) because we are using an array of size n where each position stores number of ways to reach till that position.

Translate ยป