aboutsummaryrefslogtreecommitdiff
path: root/cherry_pickup2.py
diff options
context:
space:
mode:
Diffstat (limited to 'cherry_pickup2.py')
-rw-r--r--cherry_pickup2.py48
1 files changed, 48 insertions, 0 deletions
diff --git a/cherry_pickup2.py b/cherry_pickup2.py
new file mode 100644
index 0000000..10995e1
--- /dev/null
+++ b/cherry_pickup2.py
@@ -0,0 +1,48 @@
+# 1463. Cherry Pickup II
+
+"""
+given a row cols matrix grid representing a field of cherries where
+'grid[i][j]' represents the number of cherries that you can collect from the
+'(i, j)' cell. you have two robots that can collect cherries for you located
+at corner (0, 0) and (cols - 1). return the maximum number of cherries
+collection using both robots by following the rulew below.
+"""
+
+
+class Solution(object):
+ def cherryPickup(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: int
+ """
+ m, n = len(grid), len(grid[0])
+
+ #@lru_cache(None)
+ def dfs(r, c1, c2):
+ if r == m:
+ return 0
+ cherries = grid[r][c1] if c1 == c2 else grid[r][c1] + grid[r][c2]
+ ans = 0
+ for nc1 in range(c1 - 1, c1 + 2):
+ for nc2 in range(c2 - 1, c2 + 2):
+ if 0 <= nc1 < n and 0 <= nc2 < n:
+ ans = max(ans, dfs(r + 1, nc1, nc2))
+ return ans + cherries
+
+ return dfs(0, 0, n - 1)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.cherryPickup(grid=[[3, 1, 1], [2, 5, 1], [1, 5, 5], [2, 1, 1]]))
+ print(
+ obj.cherryPickup(
+ grid=[
+ [1, 0, 0, 0, 0, 0, 1],
+ [2, 0, 0, 0, 0, 3, 0],
+ [2, 0, 9, 0, 0, 0, 0],
+ [0, 3, 0, 5, 4, 0, 0],
+ [1, 0, 2, 3, 0, 0, 6],
+ ]
+ )
+ )