A child going up a staircase with n steps, can hop up 1, 2, or 3 steps at a time. How many ways can the child reach the top?
If there are zero steps, then there is one way for the child to climb the steps (i.e., do nothing.) If there are fewer than zero steps, by convention the answer is zero (i.e., the situation is impossible.).
Otherwise, the child can climb one, two or three steps. The number of ways to proceed from the current step is the sum of those possibilities. That is, we can define our recurrence as:
s(0) = 1 s(1) = 1 s(2) = 2 s(n) = s(n - 1) + s(n - 2) + s(n - 3)
This can calculate recursively (which would be very slow) or instead use dynamic programming or memoization. Simply start at 1 and apply the formula above, then go on to 2, etc., and at each stage we have already computed the necessary prerequisites.
Number of ways to reach 4th stair, a person can climb either 1 stair or 2 stairs at a time.