Algorithms for Coding Interviews in C++/

...

/

Solution: Staircase Problem

Solution: Staircase Problem

This review contains a detailed analysis of the different ways to solve the Staircase Problem.

We'll cover the following...

Solution #1: Brute Force

Press + to interact
#include <iostream>
using namespace std;
int countWays(int n) {
  if (n < 0)
    return 0;
  else if (n == 0)
    return 1;
  else
    return countWays(n-1) + countWays(n-2)+ countWays(n-3);
}
int main() {
  cout << countWays(3) << endl;
}

This solution works very similarly to the Fibonacci problem’s recursive solution. In fact, it follows the same pattern. The main idea is that if you have n stairs then you can hop either 1 step, 2 step, 3 step.

  1. If you hop 1 step then you have n−1n-1 remaining stairs
  2. If you hop 2 steps then you have n−2n-2
...
Access this course and 1400+ top-rated courses and projects.