Cherry Pickup II

Description

Given a rows x cols matrix grid representing a field of cherries. Each cell in grid represents the number of cherries that you can collect.

You have two robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0) , and Robot #2 is located at the top-right corner (0, cols-1) of the grid.

Return the maximum number of cherries collection using both robots  by following the rules below:

• From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).
• When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).
• When both robots stay on the same cell, only one of them takes the cherries.
• Both robots cannot move outside of the grid at any moment.
• Both robots should reach the bottom row in the grid.

 

Example 1:

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

Example 2:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

Example 3:

Input: grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
Output: 22

Example 4:

Input: grid = [[1,1],[1,1]]
Output: 4

 

Constraints:

• rows == grid.length
• cols == grid[i].length
• 2 <= rows, cols <= 70
• 0 <= grid[i][j] <= 100 

Solution(javascript)

// /**
//  * @param {number[][]} grid
//  * @return {number}
//  */
// const cherryPickup = function (grid) {
//   const getValue = (row, column) => {
//     if (grid[row] && grid[row][column] >= 0) {
//       return grid[row][column]
//     }
//     return 0
//   }
//   const aux = (row1, column1, row2, column2, i = 0, visited = {}) => {
//     if (row1 === grid.length && row2 === grid.length) {
//       return 0
//     }
//     if (column1 < 0 || column1 >= grid[0].length || column2 < 0 || column2 >= grid[0].length) {
//       return 0
//     }
//     if (i % 2 === 0) {
//       const key = `${row1}-${column1}`
//       if (!visited[key]) {
//         visited[key] = true
//         const res = getValue(row1, column1) + Math.max(
//           aux(row1 + 1, column1, row2, column2, i + 1, visited),
//           aux(row1 + 1, column1 - 1, row2, column2, i + 1, visited),
//           aux(row1 + 1, column1 + 1, row2, column2, i + 1, visited),
//         )
//         visited[key] = false
//         return res
//       }
//       return Math.max(
//         aux(row1 + 1, column1, row2, column2, i + 1, visited),
//         aux(row1 + 1, column1 - 1, row2, column2, i + 1, visited),
//         aux(row1 + 1, column1 + 1, row2, column2, i + 1, visited),
//       )
//     }
//     const key = `${row2}-${column2}`
//     if (!visited[key]) {
//       visited[key] = true
//       const res = getValue(row2, column2) + Math.max(
//         aux(row1, column1, row2 + 1, column2, i + 1, visited),
//         aux(row1, column1, row2 + 1, column2 - 1, i + 1, visited),
//         aux(row1, column1, row2 + 1, column2 + 1, i + 1, visited),
//       )
//       visited[key] = false
//       return res
//     }
//     return Math.max(
//       aux(row1, column1, row2 + 1, column2, i + 1, visited),
//       aux(row1, column1, row2 + 1, column2 - 1, i + 1, visited),
//       aux(row1, column1, row2 + 1, column2 + 1, i + 1, visited),
//     )
//   }
//   return aux(0, 0, 0, grid[0].length - 1)
// }


/**
 * @param {number[][]} grid
 * @return {number}
 */
const cherryPickup = function (grid) {
  const getValue = (row, column) => {
    if (grid[row] && grid[row][column] >= 0) {
      return grid[row][column]
    }
    return 0
  }
  const next = (row, column) => {
    const arr = []
    if (column - 1 >= 0) {
      arr.push([row + 1, column - 1])
    }
    arr.push(([row + 1, column]))
    if (column + 1 <= grid[0].length - 1) {
      arr.push([row + 1, column + 1])
    }
    return arr
  }
  const memo = {}
  const aux = (x1, y1, x2, y2) => {
    const key = `${x1},${y1},${x2},${y2}`
    if (memo[key] !== undefined) {
      return memo[key]
    }
    if (x1 === grid.length && x2 === grid.length) {
      return 0
    }
    let current = 0
    if (x1 === x2 && y1 === y2) {
      current = getValue(x1, y1)
    } else {
      current = getValue(x1, y1) + getValue(x2, y2)
    }
    let max = current
    for (const [nextX1, nextY1] of next(x1, y1)) {
      for (const [nextX2, nextY2] of next(x2, y2)) {
        max = Math.max(
          max, current + aux(nextX1, nextY1, nextX2, nextY2),
        )
      }
    }
    memo[key] = max
    return memo[key]
  }
  return aux(0, 0, 0, grid[0].length - 1)
}