741. Cherry Pickup
Hard
50 Points
Array
Dynamic Programming
Matrix
You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.
Return the maximum number of cherries you can collect by following the rules below:
Examples
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.lengthn == grid[i].length1 <= n <= 50grid[i][j] is -1, 0, or 1.grid[0][0] != -1grid[n - 1][n - 1] != -1
741. Cherry Pickup
Hard
50 Points
Array
Dynamic Programming
Matrix
You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.
Return the maximum number of cherries you can collect by following the rules below:
Examples
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.lengthn == grid[i].length1 <= n <= 50grid[i][j] is -1, 0, or 1.grid[0][0] != -1grid[n - 1][n - 1] != -1