Cherry Pickup II LeetCode solution in JavaScript

1
/**
2
 * @param {number[][]} grid
3
 * @return {number}
4
 */
5
var cherryPickup = function (grid) {
6
  const numOfRow = grid.length;
7
  const numOfCol = grid[0].length;
8

9
  let memo = {}; // must memorize the step result which already get, or you will get a TLE
10

11
  const dfs = (row, col1, col2) => {
12
    if (memo[`${row},${col1},${col2}`]) {
13
      // return the result once the location have already been calculated
14
      return memo[`${row},${col1},${col2}`];
15
    }
16

17
    let cherries = grid[row][col1]; // Robot #1 location
18
    if (col1 !== col2) {
19
      // when both robots stay in the same cell, only one takes the cherries.
20
      cherries += grid[row][col2];
21
    }
22

23
    if (row === numOfRow - 1) return cherries; // last row, no need to do more DFS
24

25
    let max = 0; // initial the max cherries with next row with min integer 0
26

27
    // all the possible locations with Robot #1 and Robot #2 should calculate, the max combination is 3*3=6
28
    for (let i = col1 - 1; i <= col1 + 1; i++) {
29
      // Robot #1 next step could be next row with current col-1, current col or current col+1
30
      for (let j = col2 - 1; j <= col2 + 1; j++) {
31
        // Robot #2 next step could be next row with current col-1, current col or current col+1
32
        if (i >= 0 && j >= 0 && i < numOfCol && j < numOfCol) {
33
          // Both robot next column should greater and equal than 0, less than numOfCol
34
          max = Math.max(max, dfs(row + 1, i, j)); // save the max result with all the possible locations
35
        }
36
      }
37
    }
38
    memo[`${row},${col1},${col2}`] = max + cherries; // save the result to memo
39
    return max + cherries; // return the max cherries and the current position's cherries
40
  };
41
  return dfs(0, 0, numOfCol - 1); // from row 0, Robot #1 col1 = 0(top-left corner), Robot #2 col2 = numOfCol-1(top-right corner )
42
};