[
dp
2d-array
]
BinarySearch 0593 Collecting Coins Trequel
Problem statement
https://binarysearch.com/problems/Collecting-Coins-Trequel/
Solution
Variation of Leetcode 0741. Cherry Pickup, be careful with dimensions, also if (0, 0)
cell is equal to -1
, we can return 0
.
Complexity
It is O(mn(m+n))
for time and space.
Code
class Solution:
def solve(self, grid):
n, m = len(grid), len(grid[0])
INF = -float("inf")
@lru_cache(None)
def dfs(x1, y1, x2, y2):
if x1 == y1 == x2 == y2 == 0: return grid[0][0] if grid[0][0] != -1 else INF
if not 0 <= x1 < n or not 0 <= x2 < n: return INF
if not 0 <= y1 < m or not 0 <= y2 < m: return INF
if grid[x1][y1] == -1 or grid[x2][y2] == -1: return INF
cand_next = []
for i1, j1 in [(x1, y1-1), (x1-1, y1)]:
for i2, j2 in [(x2, y2-1), (x2-1, y2)]:
cand_next.append(dfs(i1, j1, i2, j2))
return max(cand_next) + (grid[x1][y1] + grid[x2][y2])//(1 + (x1 == x2))
res = dfs(n-1, m-1, n-1, m-1)
return res if res != INF else 0