一、题目

1、题目描述

给你一个 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) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。

2、接口描述

python3

​

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:

cpp

​

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {

    }
};

3、原题链接

741. 摘樱桃

---

二、解题报告

1、思路分析

本题溯源：[P1004 NOIP2000 提高组] 方格取数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

就是朴素二维网格dp的进阶版，leetcode在把竞赛上的经典题目搬到leetcode上

正着走一次反着走一次的最大收益等价于两个人同时从起点出发，到达终点的最大收益，这和NOIP那道题一模一样

对于一个人走我们定义f(i, j)为走到(i, j)的最大收益

两个人走，我们定义f(i, j, x, y)为A走到(i, j)B走到(x, y)的最大收益

考虑二人最终到达终点走的步数一样，可以优化状态为f(k, i, j)为两人都走k步，A走到(i, k - i)，B走到(j, k - j)时的最大收益

每个人的上一个位置有两种，那么前驱状态就有四个，我们进行递推即可

由于递推要考虑边界，这里省事直接用记忆化搜索

2、复杂度

时间复杂度： O(n^3)空间复杂度：O(n^3)

3、代码详解

python3

​

class Solution:
    def cherryPickup(self, g: List[List[int]]) -> int:
        n = len(g)
        @cache 
        def dfs(k: int, i: int, j: int) -> int:
            if k < i or k < j or i < 0 or j < 0 or g[i][k - i] < 0 or g[j][k - j] < 0:
                return -inf

            if not k:
                return g[0][0]
            
            return max(dfs(k - 1, i, j), dfs(k - 1, i - 1, j), dfs(k - 1, i, j - 1), dfs(k - 1, i - 1, j - 1)) + g[i][k - i] + (g[j][k - j] if i != j else 0)
        return max(dfs(n * 2 - 2, n - 1, n - 1), 0)

cpp

​

class Solution {
public:
static constexpr int N = 55, inf = 0x3f3f3f3f;
int f[N << 1][N][N];
    int cherryPickup(vector<vector<int>>& g) {
        memset(f, -1, sizeof f);
        int n = g.size();
        function<int(int, int, int)> dfs = [&](int k, int i, int j){
            if (k < i || k < j || i < 0 || j < 0 || g[i][k - i] < 0 || g[j][k - j] < 0)
                return -inf;
            if(!k) return g[0][0];
            int& res = f[k][i][j];
            if(~res) return res;
            res = max(max(dfs(k - 1, i, j), dfs(k - 1, i - 1, j)), max(dfs(k - 1, i, j - 1), dfs(k - 1, i - 1, j - 1))) + g[i][k - i] + (i != j) * g[j][k - j];
            return res;
        };
        return max(dfs(n * 2 - 2, n - 1, n - 1), 0);
    }
};