We already know we need a base case, a recursive definition, and a way to cache the repeating subproblems.

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.

Let's first see the brute-force solution:

function chaosInTheGrid(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  function pathsToCoord(row, col) {
    if (row === 0 || col === 0) {
      return 1;
    }
    return pathsToCoord(row - 1, col) + pathsToCoord(row, col - 1);
  }

  return pathsToCoord(rows - 1, cols - 1);
}

Next, let's use a Map for memoization:

function chaosInTheGrid(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const cache = new Map();

  function pathsToCoord(row, col) {
    if (row === 0 || col === 0) {
      return 1;
    }

    const key = `${row} ${col}`;

    if (cache.has(key)) {
      return cache.get(key);
    }

    const paths = pathsToCoord(row - 1, col) + pathsToCoord(row, col - 1);

    cache.set(key, paths);

    return paths;
  }

  return pathsToCoord(rows - 1, cols - 1);
}

Finally, we'll show you the solution using a nested array as a cache.

function chaosInTheGrid(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  // Initialize a cache as a nested array filled with zeroes
  const cache = new Array(rows).fill().map(() => new Array(cols).fill(0));

  function pathsToCoord(row, col) {
    if (row === 0 || col === 0) {
      return 1;
    }

    if (cache[row][col] !== 0) {
      return cache[row][col];
    }

    cache[row][col] = pathsToCoord(row - 1, col) + pathsToCoord(row, col - 1);

    return cache[row][col];
  }

  return pathsToCoord(rows - 1, cols - 1);
}

The brute force recursive approach's time complexity without memoization is exponential, O(2^(R + C)), as we have to explore overlapping subproblems many times. R stands for the number of rows, and C stands for the number of columns.

The space complexity for this approach with memoization is O(R + C). This is because the maximum depth of the recursion stack occurs when the recursion follows a path from the top-left to the bottom-right corner, which is R + C - 1 deep.

The time and space complexities are identical for the bottom-up and the top-down approaches, both with memoization. Every grid cell needs to be calculated once, and we are filling a cache object with the same number of values, so both the time and space complexities are O(R * C).

Note that we don't use O(N^2) as we are dealing with two separate values here, rows and columns.