Search⌘ K
Home
Courses
Grokking Dynamic Programming Interview in Python

Staircase Problem

Explore the staircase problem to understand how to count the number of ways a child can climb stairs by hopping 1, 2, or 3 steps at a time. Learn to optimize naive recursive solutions using dynamic programming techniques like memoization and tabulation. Discover how to analyze time and space complexities and improve efficiency by reducing space to constant using Fibonacci series insights.

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
...