diff options
Diffstat (limited to 'cherry_pickup2.py')
-rw-r--r-- | cherry_pickup2.py | 48 |
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], + ] + ) + ) |