Search⌘ K
Home
Courses
Grokking Dynamic Programming Interview

Staircase Problem

Explore how to determine the number of ways a child can climb stairs by hopping 1, 2, or 3 steps using recursive and dynamic programming techniques. Understand naive recursive solutions and optimize them with memoization and tabulation to improve time and space complexity. Gain practical skills in applying these patterns to solve staircase problems efficiently.

We'll cover the following...

Statement

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Your task is to count the number of possible ways that the child can climb up the stairs.

Let’s say the child has to climb three stairs. There are four ways to do it.

  • Three consecutive hops of 11 step each: 1+1+1=31+1+1 =3
  • One hop of 11 step and one hop of 22 steps: 1+2=31+2=3
  • One hop of 22 steps and one hop of 11 step: 2+1=32+1=3
  • One hop of 33 steps: 3=33=3

To clarify the basis of the calculation, we define these rules:

  • If n=0n = 0, we are already at the top of the stairs, and need to take 00 steps. We will define this as 11 way.
  • If n=1n = 1, we can take 11 step to reach the top of the stairs. There is no other way to reach the top, so we have
...