Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Staircase Problem

Explore multiple dynamic programming approaches to solve the staircase problem, including brute force, memoization, tabulation, and space optimization. Understand how these methods improve performance and handle large inputs, helping you craft efficient Java solutions for coding interviews.

We'll cover the following...

Solution #1: Brute force

Let’s look at the brute force solution first:

Java
class StairCaseProblem
{ 
  //returning count of ways to reach the nth stair
  //either using 1 hop, 2 hops or 3 hops
  public static 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);
  }
  //main function
  public static void main(String args[]) 
  {
    System.out.println(countWays(3));
  }
};

Explanation

The main idea is that if you have n stairs, then you can hop either 1 step, 2 steps or 3 steps.

  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 remaining stairs
  3. If you hop 3 steps, then you have n−3n-3
...