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

Constraints:

  • 11 \leq n 40\leq 40

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.