Lessons learned: recursion, memoization
Question 2: 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.
Instead of starting from the bottom of the staircase, let’s try to think about the last step the child takes. The last step can be a one-step , a two-step, or a three-step. Let’s write out the cases below:
Step (n-1): 1 step to reach the end of the staircase
Step (n-2): 2 steps to reach the end of the staircase
Step (n-3): 3 steps to reach the end of the staircase
But how does the child get to the n-1, n-2 or n-3rd step?
You can think of this question as a smaller form of the overall question. This is where we can utilize the concept of recursion. Recursion is when you define a question in terms of itself but in a smaller form or method. In our case, we will define the step problem in terms of itself in a smaller step:
countWays(n) = countWays(n - 1) + countWays(n - 2) + countWays(n - 3)
The last step we need to figure out is what to return for the base step. What should countWays(0) be? That is, how many steps does it take to get to the 0th step? 1? 0?
We can actually use either answer here. I ended up going with 1, since it’s easier to write out the answer and there are more base cases you have to go through if the base case is 0.
Below is a simple implementation of the method:
This solution technically works, but we can see that countWays is called several times for the same values. We can fix this through memoization.
Memoization is when you store the result of a function call and return the saved result when the function is called again. In other words, if we see countWays(n) again, we return the saved, or cached value. We can use an integer array called
memo to store, where
memo[n] = countWays(n).