Base Case

What could be the base case for this problem?

Just like in the bottom-up approach, where we populated the first row and column with 1s, this can also serve as our base case in the top-down approach.

Base Case: If we're considering a square in the first row (the first subarray in the grid) or the first column (the first element in each subarray in the grid), return 1.

Recursive Definition

What about the recursive definition? This is usually harder to come up with.

Put yourself in Chaos's shoes. If he is standing at the bottom-right square and he knows the number of unique paths to get to all other squares, what is the number of unique paths to reach that bottom-right square?

Recursive Definition: The number of unique paths to get to the bottom-right square is the sum of the number of paths to get to the square immediately above it plus the number of distinct paths to get to the square immediately to its left.

Memoization

Finally, what can we use to cache the repetitive computations? The Map could work, and that's what we'll use here. We know the value should be the number of distinct paths, but what should the keys be?

In this case, the key can be the coordinates of the square. How can we represent those coordinates? Using an array wouldn't be a good choice as two arrays with the same values are not considered equal, so that wouldn't work with our Map. We can create a string from the coordinates separated by a space. For the first square, it would look like this:

cache = {
  "0 0": 1
}

Another option is to use a nested array as a cache, just like we did in the bottom-up approach, to fill in the values as we moved through the grid. In this case, we would initialize a cache as a nested array. We can fill it with zeroes since we know there is at least one path to the bowl of treats. If the value in the array is zero, it means it hasn't been cached yet.