Staircase Problem

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 $1$ step each: $1+1+1 =3$
• One hop of $1$ step and one hop of $2$ steps: $1+2=3$
• One hop of $2$ steps and one hop of $1$ step: $2+1=3$
• One hop of $3$ steps: $3=3$

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

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

Constraints:

• $1 \leq$ n $\leq 40$