Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Staircase Problem

Explore the staircase problem through different dynamic programming solutions. Learn to implement brute force, memoization, tabulation, and space-optimized approaches while understanding their time complexities and practical considerations like integer overflow.

We'll cover the following...

Solution #1: Brute Force

C++
#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−2
...