Hard

题目描述

给你一个 n x n 的网格 grid，代表一片樱桃地，每个格子是以下三个值之一：

  • 0 表示这个格子是空的，所以你可以穿过它。
  • 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
  • -1 表示这个格子里有荆棘，挡着你的路。

请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：

  • 从位置 (0, 0) 出发，最后到达 (n-1, n-1) ，只能向下或向右走，并且只能穿越有效的格子（即值为 0 或者 1 的格子）；
  • 当到达 (n-1, n-1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
  • 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）；
  • 如果在 (0, 0) 和 (n-1, n-1) 之间不存在一条有效的路径，则没有任何樱桃可以摘到。

示例 1：

输入：grid = [[0,1,-1],[1,0,-1],[1,1,1]]
输出：5
解释：玩家从 (0, 0) 出发：向下，向下，向右，向右移动至 (2, 2) 。
在这一次行程中捡到 4 个樱桃，矩阵变成 [[0,1,-1],[0,0,-1],[0,0,0]] 。
接着，玩家向左，向上，向上，向左返回起点，又捡到 1 个樱桃。
总共捡到 5 个樱桃，这是最大可能值。

示例 2：

输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
输出：0

提示：

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 50
  • grid[i][j] 为 -1、0 或 1
  • grid[0][0] != -1
  • grid[n - 1][n - 1] != -1

解题思路

这道题的核心思路是将问题转化为两人同时从起点出发到终点的路径问题。

关键洞察： 一个人从 (0,0) 到 (n-1,n-1) 再返回 (0,0) 等价于两个人同时从 (0,0) 出发到 (n-1,n-1)，每个人只能向右或向下移动。这样转化的好处是避免了处理樱桃被摘掉后状态变化的复杂性。

动态规划设计：

  • 状态：dp[i1][j1][i2][j2] 表示第一个人走到 (i1,j1)，第二个人走到 (i2,j2) 时能获得的最大樱桃数
  • 由于两人同步移动，步数相同：i1 + j1 = i2 + j2 = k，所以可以优化为三维：dp[k][i1][i2]，其中 j1 = k - i1，j2 = k - i2
  • 状态转移：考虑两人的四种移动组合（右右、右下、下右、下下）
  • 樱桃收集：如果两人在同一位置且有樱桃，只能收集一次；否则分别收集各自位置的樱桃

边界条件：

  • 遇到荆棘（-1）则该路径无效
  • 初始状态：dp[0][0][0] = grid[0][0]
  • 最终答案：dp[2n-2][n-1][n-1]

推荐解法： 使用记忆化搜索实现，代码更清晰易懂。

代码实现

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<vector<int>>> memo(n, vector<vector<int>>(n, vector<int>(n, -1)));
        
        function<int(int, int, int)> dp = [&](int i1, int j1, int i2) -> int {
            int j2 = i1 + j1 - i2;
            
            if (i1 >= n || j1 >= n || i2 >= n || j2 >= n || 
                grid[i1][j1] == -1 || grid[i2][j2] == -1) {
                return -1000000;
            }
            
            if (i1 == n-1 && j1 == n-1) {
                return grid[i1][j1];
            }
            
            if (memo[i1][j1][i2] != -1) {
                return memo[i1][j1][i2];
            }
            
            int result = max({
                dp(i1+1, j1, i2+1),
                dp(i1+1, j1, i2),
                dp(i1, j1+1, i2+1),
                dp(i1, j1+1, i2)
            });
            
            if (result < 0) {
                return memo[i1][j1][i2] = -1000000;
            }
            
            result += grid[i1][j1];
            if (i1 != i2) {
                result += grid[i2][j2];
            }
            
            return memo[i1][j1][i2] = result;
        };
        
        return max(0, dp(0, 0, 0));
    }
};

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        memo = {}
        
        def dp(i1, j1, i2):
            j2 = i1 + j1 - i2
            
            if (i1 >= n or j1 >= n or i2 >= n or j2 >= n or 
                grid[i1][j1] == -1 or grid[i2][j2] == -1):
                return float('-inf')
            
            if i1 == n-1 and j1 == n-1:
                return grid[i1][j1]
            
            if (i1, j1, i2) in memo:
                return memo[(i1, j1, i2)]
            
            result = max(
                dp(i1+1, j1, i2+1),
                dp(i1+1, j1, i2),
                dp(i1, j1+1, i2+1),
                dp(i1, j1+1, i2)
            )
            
            if result == float('-inf'):
                memo[(i1, j1, i2)] = result
                return result
            
            result += grid[i1][j1]
            if i1 != i2:
                result += grid[i2][j2]
            
            memo[(i1, j1, i2)] = result
            return result
        
        return max(0, dp(0, 0, 0))

public class Solution {
    public int CherryPickup(int[][] grid) {
        int n = grid.Length;
        int[,,] memo = new int[n, n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    memo[i, j, k] = int.MinValue;
                }
            }
        }
        
        int Dp(int i1, int j1, int i2) {
            int j2 = i1 + j1 - i2;
            
            if (i1 >= n || j1 >= n || i2 >= n || j2 >= n || 
                grid[i1][j1] == -1 || grid[i2][j2] == -1) {
                return -1000000;
            }
            
            if (i1 == n-1 && j1 == n-1) {
                return grid[i1][j1];
            }
            
            if (memo[i1, j1, i2] != int.MinValue) {
                return memo[i1, j1, i2];
            }
            
            int result = Math.Max(Math.Max(
                Dp(i1+1, j1, i2+1),
                Dp(i1+1, j1, i2)),
                Math.Max(
                Dp(i1, j1+1, i2+1),
                Dp(i1, j1+1, i2))
            );
            
            if (result < 0) {
                return memo[i1, j1, i2] = -1000000;
            }
            
            result += grid[i1][j1];
            if (i1 != i2) {
                result += grid[i2][j2];
            }
            
            return memo[i1, j1, i2] = result;
        }
        
        return Math.Max(0, Dp(0, 0, 0));
    }
}

var cherryPickup = function(grid) {
    const n = grid.length;
    const memo = new Map();
    
    function dp(i1, j1, i2) {
        const j2 = i1 + j1 - i2;
        
        if (i1 >= n || j1 >= n || i2 >= n || j2 >= n || 
            grid[i1][j1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n³) - 三维状态空间，每个状态计算一次
空间复杂度O(n³) - 记忆化数组存储所有可能的状态

相关题目