Solution to LeetCode 741 Cherry Pickup.
LeetCode 741
Cherry Pickup (Hard). [link]
Keys to tackle this problem:
1] Since the problem states that the grid is an N by N 2D array, with 1 <= N <= 50, we can not search (N <= 10, it’s safe to use search).
2] Going from (0,0) to (n-1, n-1) is the same as going from (n-1, n-1) to (0,0). Going forwards and backwards is the same as going backwards twice or two people go backwards. Notice that when they go backwards, if they meet at the same grid with a cherry, only one cherry is counted.
3] There should be two paths (or two positions (x1, y1) and (x2, y2)). We can observe that at each move, these two people are always on the same diagonal line. So we can use three points x1, x2, y1 to represent the two positions, rather than using four points.
4] The state of dynamic programming can be stored in dp[x1, y1, x2], which indicating the max number of cherries picked up so far.
Recursion with memoization. Time complexity O(n^3). Space complexity O(n^3).
class Solution(object):
def cherryPickup(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
n = len(grid)
dp = [[[float('-inf')] * n for _ in range(n)] for _ in range(n)]
def Recursion(x1, y1, x2):
y2 = x1 + y1 - x2
if x1 < 0 or x2 < 0 or y1 < 0 or y2 < 0: # out of bound
return -1
if grid[x1][y1] < 0 or grid[x2][y2] < 0: # -1, blocked
return -1
if x1 == 0 and y1 == 0: # reach the end
return grid[x1][y1]
if dp[x1][y1][x2] != float('-inf'): # memoization
return dp[x1][y1][x2]
res = max(
max(Recursion(x1 - 1, y1, x2 - 1), Recursion(x1, y1 - 1, x2)),
max(Recursion(x1, y1 - 1, x2 - 1), Recursion(x1 - 1, y1, x2))
) # best move to get most cherries
if res < 0: # cannot find best move, or all moves are blocked
dp[x1][y1][x2] = -1
else:
res += grid[x1][y1] # no duplicate count of cherry
if x1 != x2:
res += grid[x2][y2]
dp[x1][y1][x2] = res
return dp[x1][y1][x2]
return max(0, Recursion(n-1, n-1, n-1))
