题目大意：
摘樱桃 II
给你一个 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 最底下一行。
示例 1：
输入：grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]] 输出：24 解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。 机器人 1 摘的樱桃数目为 (3 + 2 + 5 + 2) = 12 。 机器人 2 摘的樱桃数目为 (1 + 5 + 5 + 1) = 12 。 樱桃总数为： 12 + 12 = 24 。
示例 2：
输入：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]] 输出：28 解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。 机器人 1 摘的樱桃数目为 (1 + 9 + 5 + 2) = 17 。 机器人 2 摘的樱桃数目为 (1 + 3 + 4 + 3) = 11 。 樱桃总数为： 17 + 11 = 28 。
示例 3：
输入：grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]] 输出：22
示例 4：
输入：grid = [[1,1],[1,1]] 输出：4
提示：
- rows == grid.length
- cols == grid[i].length
- 2 <= rows, cols <= 70
- 0 <= grid[i][j] <= 100
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1463
解题思路分析：
类似这种每一步都有很多种选择，并且需要在多种选择中挑选出最优解的题目，绝大情况下是需要采用动态规划思路来解题的。本题就是一个经典的案例。由于我个人更青睐于使用递归加记忆数组的方式解DP题目，所以本题也会使用该方式来做讲解。
我们创建一个递归函数，参数中传入两个机器人当前的坐标，初始值为(0,0)与(0, cols-1)两点。每一步递归中，先收集两个机器人当前所在位置上的樱桃（注意如果两个机器人位于同一点时，只收一次）。然后让两个机器人同时向下一行迈出一格，因为每个机器人都各有3种选择（左下，正下或者右下），因此两个机器人同时移动一步后，理论上共存在9种可能。我们除去越界的选择外，循环剩下的每种选择，将机器人的位置更新后传入递归函数。循环中递归函数返回值中的最大值即是当前最优解，最优解加上本层递归收集到的樱桃数即是本层递归的返回值。
最后再来考虑记忆数组，本题递归函数中存在4个变量，即两个机器人的横纵坐标，因此我们需要建立一个4维数组来记录当前递归函数的解。另外这里存在一个可以优化的地方，因为两个机器人不论如何移动，他们始终保持在同一行，因此我们可以将数组降维至3维，即横坐标与两个机器人所在的纵坐标。
如果你仍然无法理解我上面的逻辑，那么说明你对dp或是递归还没有深入的理解。强烈建议你去参考一下我之前总结过的文章：
实现代码：
int[][] dirs=new int[][]{{1,-1},{1,0},{1,1}}; // 可移动的方向
Integer[][][] memo; // 记忆数组
public int cherryPickup(int[][] grid) {
// 初始化记忆数组
memo=new Integer[grid.length][grid[0].length][grid[0].length];
// 递归求解
return help(grid,0,0,grid[0].length-1);
}
// grid：地图
// r1：当前行
// c1：机器人1所在列
// c2：机器人2所在列
// 返回值：从当前位置到最后一行间能采摘到最多的樱桃数
int help(int[][] grid,int r1,int c1,int c2){
// 如果记忆数组中存在当前解，返回记忆数组中的值
if(memo[r1][c1][c2]!=null) return memo[r1][c1][c2];
// 采摘机器人1所在位置的樱桃，并累加至返回结果
int res=grid[r1][c1];
// 如果两个机器人不在同一位置，采摘第二个机器人所在位置的樱桃
if(c1!=c2) res+=grid[r1][c2];
int max=0; // 最优解
for(int[] d1 : dirs){ // 循环第一个机器人下一步的三种选择
int row1=r1+d1[0],col1=c1+d1[1]; // 机器人1下一步坐标
if(row1==grid.length) break; // 如果行越界，退出
if(col1<0||col1==grid[0].length) continue; // 如果列越界，继续
for(int[] d2 : dirs){ // 循环第二个机器人下一步的三种选择
int col2=c2+d2[1]; // 机器人2下一步坐标
if(col2<0||col2==grid[0].length) continue; // 如果列越界，继续
// 利用两个机器人下一步坐标，递归至子函数
// 并利用递归返回值更新最大值
max=Math.max(max,help(grid,row1,col1,col2));
}
}
res+=max; // 返回结果加上最大值
memo[r1][c1][c2]=res; // 将返回结果计入记忆数组
return res;
} 本题解法执行时间为17ms
Runtime: 17 ms, faster than 76.53% of Java online submissions for Cherry Pickup II.
Memory Usage: 39.1 MB, less than 100.00% of Java online submissions for Cherry Pickup II.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1463-cherry-pickup-ii-解题思路分析/