1463.摘樱桃II

链接：1463.摘樱桃II
难度：Hard
标签：数组、动态规划、矩阵
简介：你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。请你按照如下规则，返回两个机器人能收集的最多樱桃数目。

题解 1 - python

• 编辑时间：2024-05-07
• 执行用时：871ms
• 内存消耗：57.7MB
• 编程语言：python
• 解法介绍：dfs记录当前x坐标下，第一个人在y1，第二个人在y2时的最大樱桃数。

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        dirs = [1, 0, -1]
        @cache
        def dfs(x: int, y1: int, y2: int) -> int:
            if x == n: return 0
            res = 0
            for dir in dirs:
                ny1 = y1 + dir
                if 0 <= ny1 < m:
                    for dir in dirs:
                        ny2 = y2 + dir
                        if 0 <= ny2 < m:
                            res = max(res, dfs(x + 1, ny1, ny2))
            res += grid[x][y1]
            if y1 != y2: res += grid[x][y2]
            return res
        return dfs(0, 0, m - 1)