目录

一、题目

1、题目描述

2、接口描述

python3

cpp

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

python3

cpp

---

一、题目

1、题目描述

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则，返回两个机器人能收集的最多樱桃数目：

• 从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
• 当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
• 当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
• 两个机器人在任意时刻都不能移动到 grid 外面。
• 两个机器人最后都要到达 grid 最底下一行。

2、接口描述

python3

​

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

cpp

​

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

3、原题链接

1463. 摘樱桃 II

---

二、解题报告

1、思路分析

和昨天的每日一题一样的思路，二者只能往左下，右下，下三个方向走，那么走同样步数的情况下二者处于同一层

我们定义状态f(i, j, k)表示robot1走到(i, j)，robot2走到(i, k)时的最大收益

那么有递推：f(i, j, k) = max(dfs(i + 1, j, k), dfs(i + 1, j, k + 1), dfs(i + 1, j, k - 1), 
                            dfs(i + 1, j + 1, k), dfs(i + 1, j + 1, k + 1), dfs(i + 1, j + 1, k - 1),
                                dfs(i + 1, j - 1, k), dfs(i + 1,j - 1, k + 1), dfs(i + 1, j - 1, k - 1)) + grid[i][j] + (grid[i][k] if j != k else 0)

我们可以选择记忆化搜索也可以选择递推的方式，二者皆可

2、复杂度

时间复杂度： O(m * n * n)空间复杂度：O(m * n * n)

3、代码详解

python3

​

class Solution:def cherryPickup(self, grid: List[List[int]]) -> int:m = len(grid)n = len(grid[0])@cachedef dfs(i: int, j: int, k: int) -> int:if i >= m or j < 0 or j >= n or k < 0 or k >= n:return 0return max(dfs(i + 1, j, k), dfs(i + 1, j, k + 1), dfs(i + 1, j, k - 1), dfs(i + 1, j + 1, k), dfs(i + 1, j + 1, k + 1), dfs(i + 1, j + 1, k - 1),dfs(i + 1, j - 1, k), dfs(i + 1,j - 1, k + 1), dfs(i + 1, j - 1, k - 1)) + grid[i][j] + (grid[i][k] if j != k else 0)return dfs(0, 0, n - 1)

cpp

​

class Solution {
public:int cherryPickup(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<vector<int>>> f(m, vector<vector<int>>(n, vector<int>(n, -1)));function<int(int, int, int)> dfs = [&](int i, int j, int k){if(i >= m || j < 0 || j >= n || k < 0 || k >= n) return 0;int& res = f[i][j][k];if(~res) return res;res = grid[i][j] + (j != k) * grid[i][k] + max({ dfs(i + 1, j, k), dfs(i + 1, j, k + 1), dfs(i + 1, j, k - 1), dfs(i + 1, j + 1, k), dfs(i + 1, j + 1, k + 1), dfs(i + 1, j + 1, k - 1),dfs(i + 1, j - 1, k), dfs(i + 1,j - 1, k + 1), dfs(i + 1, j - 1, k - 1) });return res;};return dfs(0, 0, n - 1);}
};