Algorithm

Problem Name: 741. Cherry Pickup

Problem Link:  https://leetcode.com/problems/cherry-pickup/
 

You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.

  • 0 means the cell is empty, so you can pass through,
  • 1 means the cell contains a cherry that you can pick up and pass through, or
  • -1 means the cell contains a thorn that blocks your way.

Return the maximum number of cherries you can collect by following the rules below:

  • Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with value 0 or 1).
  • After reaching (n - 1, n - 1), returning to (0, 0) by moving left or up through valid path cells.
  • When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell 0.
  • If there is no valid path between (0, 0) and (n - 1, n - 1), then no cherries can be collected.

 

Example 1:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.

Example 2:

Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 0

 

Constraints:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 50
  • grid[i][j] is -1, 0, or 1.
  • grid[0][0] != -1
  • grid[n - 1][n - 1] != -1

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const cherryPickup = grid => {
  const n = grid.length
  const dp = [...new Array(n)].map(() =>
    [...new Array(n)].map(() => Array(n).fill(-Infinity))
  )
  dp[0][0][0] = grid[0][0]
  const go = (x1, y1, x2) => {
    const y2 = x1 + y1 - x2
    if (x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0) return -1
    if (grid[y1][x1] === -1 || grid[y2][x2] === -1) return -1
    if (dp[y1][x1][x2] !== -Infinity) return dp[y1][x1][x2]
    dp[y1][x1][x2] = Math.max(
      go(x1 - 1, y1, x2 - 1),
      go(x1, y1 - 1, x2),
      go(x1, y1 - 1, x2 - 1),
      go(x1 - 1, y1, x2)
    )
    if (dp[y1][x1][x2] >= 0) {
      dp[y1][x1][x2] += grid[y1][x1]
      if (x1 !== x2) dp[y1][x1][x2] += grid[y2][x2]
    }
    return dp[y1][x1][x2]
  }
  return Math.max(0, go(n - 1, n - 1, n - 1))
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
rid = [[0,1,-1],[1,0,-1],[1,1,1]]

Output

x
–
+
cmd
5

#2 Code Example with Python Programming

Code - Python Programming


class Solution(object):
    def cherryPickup(self, grid):
        if grid[-1][-1] == -1: return 0
        memo, n = {}, len(grid)
        def dp(i1, j1, i2, j2):
            if (i1, j1, i2, j2) in memo: return memo[(i1, j1, i2, j2)]
            if n in (i1, j1, i2, j2) or -1 in (grid[i1][j1], grid[i2][j2]): return -1
            if i1 == i2 == j1 == j2 == n - 1: return grid[-1][-1]
            mx = max(dp(i1+1, j1, i2+1, j2), dp(i1+1, j1, i2, j2+1), dp(i1, j1+1, i2+1, j2), dp(i1, j1+1, i2, j2+1))
            if mx == - 1: out = -1 
            elif i1 == i2 and j1 == j2: out = mx + grid[i1][j1]
            else: out = mx + grid[i1][j1] + grid[i2][j2]
            memo[(i1, j1, i2, j2)] = out
            return out
        return max(0, dp(0, 0, 0, 0))
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
rid = [[0,1,-1],[1,0,-1],[1,1,1]]

Output

x
–
+
cmd
5
Advertisements

Demonstration

Previous
#740 Leetcode Delete and Earn Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#743 Leetcode Network Delay Time Solution in C, C++, Java, JavaScript, Python, C# Leetcode