Count how many possible ways the child can run up the stairs

Problem

A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

How to Solve

This problem can be solved efficiently by Dynamic Programming. The idea is composed by the following steps.

1. Prepare the memo table

First, we prepare the memo table to keep the count of the ways that a child can run up the stairs from the current position. So, the index of memo array corresponds to current position and the value of memo array corresponds to count of the ways.

Define the recursive function

Second, we defined recursive function. The child can hop 3 three way so that the method is called in itself.