Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/741.html
741. Cherry Pickup
Level
Hard
Description
In a 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;
- -1 means the cell contains a thorn that blocks your way.
Your task is to collect maximum number of cherries possible 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.
Note:
gridis anNbyN2D array, with1 <= N <= 50.- Each
grid[i][j]is an integer in the set{-1, 0, 1}. - It is guaranteed that
grid[0][0]andgrid[N-1][N-1]are not -1.
Solution
This problem is equivalent to finding two paths from position (0, 0) to position (N-1, N-1). If a cell that contains a cherry is in both paths, then the cherry in the cell can only be collected once.
Use dynamic programming. Suppose two paths are simultaneous. At the same time, suppose the cell in the first path is (i, j) and the cell in the second path is (k, m), then there is i + j == k + m, where i, j, k and m are all greater than and equal to 0 and less than N. Therefore, maintain a 3D array dp with size N x N x N, where all the values are -1 initially. Set dp[0][0][0] = grid[0][0]. Then for each tuple (i, j, k), calculate m = i + j - k. If k <= i + j and 0 <= m < N, and both grid[i][j] and grid[k][m] are greater than or equal to 0, consider all four possible cases to reach the current state (either path can be moving right or moving down in the last move), calculate the maximum value of total cherries that can be picked up, and assign the value to dp[i][j][k] if it is not negative.
Finally, obtain the value dp[N - 1][N - 1][N - 1]. If the value is negative, return 0. Otherwise, return the value.
-
class Solution { public int cherryPickup(int[][] grid) { int length = grid.length; int[][][] dp = new int[length][length][length]; for (int i = 0; i < length; i++) { for (int j = 0; j < length; j++) { for (int k = 0; k < length; k++) dp[i][j][k] = -1; } } dp[0][0][0] = grid[0][0]; for (int i = 0; i < length; i++) { for (int j = 0; j < length; j++) { int kMax = Math.min(i + j, length - 1); for (int k = 0; k <= kMax; k++) { int m = i + j - k; if (m < 0 || m >= length) continue; if (grid[i][j] == -1 || grid[k][m] == -1) continue; int num1 = i == 0 || k == 0 ? -1 : dp[i - 1][j][k - 1]; int num2 = i == 0 ? -1 : dp[i - 1][j][k]; int num3 = j == 0 || k == 0 ? -1 : dp[i][j - 1][k - 1]; int num4 = j == 0 ? -1 : dp[i][j - 1][k]; int currentCherries = max(num1, num2, num3, num4); if (currentCherries < 0) continue; currentCherries += grid[i][j]; if (i != k || j != m) currentCherries += grid[k][m]; dp[i][j][k] = currentCherries; } } } return Math.max(0, dp[length - 1][length - 1][length - 1]); } public int max(int num1, int num2, int num3, int num4) { return Math.max(Math.max(Math.max(num1, num2), num3), num4); } } -
// OJ: https://leetcode.com/problems/cherry-pickup/ // Time: O(N^3) // Space: O(N^3) // Ref: https://leetcode.com/problems/cherry-pickup/solution/ class Solution { public: int cherryPickup(vector<vector<int>>& A) { int N = A.size(), memo[51][51][51] = {}; // INT_MIN = non-reachable, -1 = unvisited memset(memo, -1, sizeof(memo)); function<int(int, int, int)> dp = [&](int r1, int c1, int c2) { int r2 = r1 + c1 - c2; if (r1 == N || r2 == N || c1 == N || c2 == N || A[r1][c1] == -1 || A[r2][c2] == -1) return INT_MIN; // If out-of-bound or non-reachable, return -Infinity if (r1 == N - 1 && c1 == N - 1) return A[r1][c1]; if (memo[r1][c1][c2] != -1) return memo[r1][c1][c2]; int ans = A[r1][c1]; if (c1 != c2) ans += A[r2][c2]; ans += max({ dp(r1, c1 + 1, c2 + 1), dp(r1, c1 + 1, c2), dp(r1 + 1, c1, c2 + 1), dp(r1 + 1, c1, c2) }); return memo[r1][c1][c2] = ans; }; return max(0, dp(0, 0, 0)); } }; -
class Solution: def cherryPickup(self, grid: List[List[int]]) -> int: n = len(grid) dp = [[[-inf] * n for _ in range(n)] for _ in range((n << 1) - 1)] dp[0][0][0] = grid[0][0] for k in range(1, (n << 1) - 1): for i1 in range(n): for i2 in range(n): j1, j2 = k - i1, k - i2 if ( not 0 <= j1 < n or not 0 <= j2 < n or grid[i1][j1] == -1 or grid[i2][j2] == -1 ): continue t = grid[i1][j1] if i1 != i2: t += grid[i2][j2] for x1 in range(i1 - 1, i1 + 1): for x2 in range(i2 - 1, i2 + 1): if x1 >= 0 and x2 >= 0: dp[k][i1][i2] = max( dp[k][i1][i2], dp[k - 1][x1][x2] + t ) return max(0, dp[-1][-1][-1]) -
func cherryPickup(grid [][]int) int { n := len(grid) dp := make([][][]int, (n<<1)-1) for i := range dp { dp[i] = make([][]int, n) for j := range dp[i] { dp[i][j] = make([]int, n) } } dp[0][0][0] = grid[0][0] for k := 1; k < (n<<1)-1; k++ { for i1 := 0; i1 < n; i1++ { for i2 := 0; i2 < n; i2++ { dp[k][i1][i2] = int(-1e9) j1, j2 := k-i1, k-i2 if j1 < 0 || j1 >= n || j2 < 0 || j2 >= n || grid[i1][j1] == -1 || grid[i2][j2] == -1 { continue } t := grid[i1][j1] if i1 != i2 { t += grid[i2][j2] } for x1 := i1 - 1; x1 <= i1; x1++ { for x2 := i2 - 1; x2 <= i2; x2++ { if x1 >= 0 && x2 >= 0 { dp[k][i1][i2] = max(dp[k][i1][i2], dp[k-1][x1][x2]+t) } } } } } } return max(0, dp[n*2-2][n-1][n-1]) } func max(a, b int) int { if a > b { return a } return b } -
/** * @param {number[][]} grid * @return {number} */ var cherryPickup = function (grid) { const n = grid.length; let dp = new Array(n * 2 - 1); for (let k = 0; k < dp.length; ++k) { dp[k] = new Array(n); for (let i = 0; i < n; ++i) { dp[k][i] = new Array(n).fill(-1e9); } } dp[0][0][0] = grid[0][0]; for (let k = 1; k < n * 2 - 1; ++k) { for (let i1 = 0; i1 < n; ++i1) { for (let i2 = 0; i2 < n; ++i2) { const j1 = k - i1, j2 = k - i2; if ( j1 < 0 || j1 >= n || j2 < 0 || j2 >= n || grid[i1][j1] == -1 || grid[i2][j2] == -1 ) { continue; } let t = grid[i1][j1]; if (i1 != i2) { t += grid[i2][j2]; } for (let x1 = i1 - 1; x1 <= i1; ++x1) { for (let x2 = i2 - 1; x2 <= i2; ++x2) { if (x1 >= 0 && x2 >= 0) { dp[k][i1][i2] = Math.max( dp[k][i1][i2], dp[k - 1][x1][x2] + t, ); } } } } } } return Math.max(0, dp[n * 2 - 2][n - 1][n - 1]); };