Cherry Pickup — LeetCode 741 Python Solution
HardArrayDynamic ProgrammingMatrix
- Problem
- #741
- Pattern
- Matrix and Grid
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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.
Example
- 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).
Python solution
Python
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
n = len(grid)
f = [[[-inf] * n for _ in range(n)] for _ in range((n << 1) - 1)]
f[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:
f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][x1][x2] + t)
return max(0, f[-1][-1][-1])Complexity
| Measure | Complexity |
|---|---|
| Time | O(n^3) |
| Space | O(n^3) auxiliary |
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 741. Cherry Pickup is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 741. Cherry Pickup?
- LeetCode 741. Cherry Pickup is rated Hard on LeetCode.
- What is the time complexity of LeetCode 741. Cherry Pickup?
- The Python solution on this page runs in O(n^3).
- What is the space complexity of LeetCode 741. Cherry Pickup?
- The Python solution on this page uses O(n^3) auxiliary space.
- What topics does LeetCode 741. Cherry Pickup cover?
- LeetCode 741. Cherry Pickup is tagged Array, Dynamic Programming and Matrix on LeetCode.