最大路径和问题（摘樱桃问题）
作者：Grey
原文地址: 最大路径和问题（摘樱桃问题）
题目链接
主要思路
本题的难点在于尝试，如何模拟一来一回的情况，我们可以这样做，定义两个小人，两个人都从(0,0)位置出发，到右下角位置，每人同时选择不同的下一步，如果两个小人跳到了同一个位置，只计算一份。由于两个小人是同时走，而且每次只走一步，所以，两个小人一定是同时到达右下角的，两个小人一路收集的樱桃数量，就是一来一回收集的数量。
我们可以写出第一个尝试版本，定义递归函数
int p(int[][] matrix, int m, int n, int x1, int y1, int x2, int y2)
递归函数的含义表示，第一个小人从(x1,y1)开始到右下角，第二个小人从(x2,y2)开始到右下角，获取到的最大值是多少。所以p(matrix, m, n, 0, 0, 0, 0)就是我们需要的答案。
接下来考虑base case，即：两个小人都到达了右下角，由于题目已经说了，右下角的值一定不是-1，所以，可以获得一份樱桃数量。
if (x1 == m - 1 && y1 == n - 1) {
// 已经到了最右下角了
// 隐含条件：另外一个点也一定到达右下角
// 获得一份樱桃数
return matrix[x1][y1];
}
接下来就是普遍尝试，分别可以分成如下四种情况：
情况1：第一个小人往下，第二个小人往右。
情况2：第一个小人往下，第二个小人往下。
情况3：第一个小人往右，第二个小人往下。
情况4：第一个小人往右，第二个小人往右。
但是在走上述任何分支的时候，记得要满足两个条件
第一个条件，不能越界
第二个条件，下一个要走的位置不能是-1，因为题目说到，-1是不能走的位置。
int next = -1;
// 下，下
if (x1 + 1 < m && x2 + 1 < m && matrix[x1 + 1][y1] != -1 && matrix[x2 + 1][y2] != -1) {
next = Math.max(p(matrix, m, n, x1 + 1, y1, x2 + 1, y2), next);
}
// 下，右
if (x1 + 1 < m && y2 + 1 < n && matrix[x1 + 1][y1] != -1 && matrix[x2][y2 + 1] != -1) {
next = Math.max(p(matrix, m, n, x1 + 1, y1, x2, y2 + 1), next);
}
// 右，下
if (y1 + 1 < n && x2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2 + 1][y2] != -1) {
next = Math.max(p(matrix, m, n, x1, y1 + 1, x2 + 1, y2), next);
}
// 右，右
if (y1 + 1 < n && y2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2][y2 + 1] != -1) {
next = Math.max(p(matrix, m, n, x1, y1 + 1, x2, y2 + 1), next);
}
经过上述四个分支，如果next的值还是-1，说明无路可走，返回-1
if (next == -1) {
return -1;
}
如果next不等于-1，说明有可以走的路径，那么继续判断两个小人是否在同一位置，如果在同一个位置，则只收集一份樱桃，如果不在同一个位置，收集两个小人所在位置的樱桃之和。
if (x1 == x2) {
// 到达同一个位置，只取一个值
return next + matrix[x1][y1];
}
return next + matrix[x1][y1] + matrix[x2][y2];
注：判断同一个位置，只需要一个维度上的坐标相等即可。
完整代码
public static int cherryPickup1(int[][] matrix) {
return Math.max(0, p(matrix, matrix.length, matrix[0].length, 0, 0, 0, 0));
}
// 定义两个小人，两个人都从(0,0)位置出发，到右下角位置，每人同时选择不同的下一步，如果两个小人跳到了同一个位置，只计算一份。
public static int p(int[][] matrix, int m, int n, int x1, int y1, int x2, int y2) {
if (x1 == m - 1 && y1 == n - 1) {
// 已经到了最右下角了
// 隐含条件：另外一个点也一定到达右下角
// 获得一份樱桃数
return matrix[x1][y1];
}
int next = -1;
// 下，下
if (x1 + 1 < m && x2 + 1 < m && matrix[x1 + 1][y1] != -1 && matrix[x2 + 1][y2] != -1) {
next = Math.max(p(matrix, m, n, x1 + 1, y1, x2 + 1, y2), next);
}
// 下，右
if (x1 + 1 < m && y2 + 1 < n && matrix[x1 + 1][y1] != -1 && matrix[x2][y2 + 1] != -1) {
next = Math.max(p(matrix, m, n, x1 + 1, y1, x2, y2 + 1), next);
}
// 右，下
if (y1 + 1 < n && x2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2 + 1][y2] != -1) {
next = Math.max(p(matrix, m, n, x1, y1 + 1, x2 + 1, y2), next);
}
// 右，右
if (y1 + 1 < n && y2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2][y2 + 1] != -1) {
next = Math.max(p(matrix, m, n, x1, y1 + 1, x2, y2 + 1), next);
}
if (next == -1) {
return -1;
}
if (x1 == x2) {
// 到达同一个位置，只取一个值
return next + matrix[x1][y1];
}
return next + matrix[x1][y1] + matrix[x2][y2];
}
这个解法在 LeetCode 上直接超时。
在上述尝试的基础上，我们可以做进一步的优化，递归函数现在是四个可变参数，根据我们的设计，其实可以得到如下公式
x1 + y1 = x2 + y2
那么我们可以将递归函数省略一个参数y2，因为
y2 = x1 + y1 - x2
上述递归方法我们可以修改为
// 省略y2参数
public static int p(int[][] matrix, int m, int n, int x1, int y1, int x2) {
if (x1 == m - 1 && y1 == n - 1) {
// 已经到了最右下角了
// 隐含条件：另外一个点也一定到达右下角
// 获得一份樱桃数
return matrix[x1][y1];
}
int next = -1;
// 下，下
if (x1 + 1 < m && x2 + 1 < m && matrix[x1 + 1][y1] != -1 && matrix[x2 + 1][getY2(x1, y1, x2)] != -1) {
next = Math.max(p(matrix, m, n, x1 + 1, y1, x2 + 1), next);
}
// 下，右
if (x1 + 1 < m && getY2(x1, y1, x2) + 1 < n && matrix[x1 + 1][y1] != -1 && matrix[x2][getY2(x1, y1, x2) + 1] != -1) {
next = Math.max(p(matrix, m, n, x1 + 1, y1, x2), next);
}
// 右，下
if (y1 + 1 < n && x2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2 + 1][getY2(x1, y1, x2)] != -1) {
next = Math.max(p(matrix, m, n, x1, y1 + 1, x2 + 1), next);
}
// 右，右
if (y1 + 1 < n && getY2(x1, y1, x2) + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2][getY2(x1, y1, x2) + 1] != -1) {
next = Math.max(p(matrix, m, n, x1, y1 + 1, x2), next);
}
if (next == -1) {
return -1;
}
if (x1 == x2) {
// 到达同一个位置，只取一个值
return next + matrix[x1][y1];
}
return next + matrix[x1][y1] + matrix[x2][getY2(x1, y1, x2)];
}
public static int getY2(int x1, int y1, int x2) {
return x1 + y1 - x2;
}
我们可以做进一步的优化，由于三个可变参数的范围分别是[0...m-1]，[0...n-1]，[0...m-1]，那么我们可以设置三维dp，将所有递归结果缓存起来
int[][][] dp = new int[m][n][m];
三维dp的所有位置初始值设置为Integer.MIN_VALUE，在递归方法中，将这个三维表作为缓存带入参数中，每次递归过程中，先从dp表中拿值，如果值不为Integer.MIN_VALUE，说明这个过程算过，直接取值即可。
public static int p(int[][] matrix, int m, int n, int x1, int y1, int x2, int[][][] dp) {
if (dp[x1][y1][x2] != Integer.MIN_VALUE) {
// 说明这个过程曾经算过，直接从缓存中取值即可
return dp[x1][y1][x2];
}
}
然后在每次递归过程中，将答案存入缓存，完整代码如下
// 动态规划
// 三维表
public static int cherryPickup(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][][] dp = new int[m][n][m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
// 初始值设置为Integer.MIN_VALUE，只要不等于Integer.MIN_VALUE，就说明递归过程已经算过了
dp[i][j][k] = Integer.MIN_VALUE;
}
}
}
return Math.max(0, p(matrix, m, n, 0, 0, 0, dp));
}
// 定义两个小人，两个人都从(0,0)位置出发，到右下角位置，每人同时选择不同的下一步，如果两个小人跳到了同一个位置，只计算一份。
public static int p(int[][] matrix, int m, int n, int x1, int y1, int x2, int[][][] dp) {
if (dp[x1][y1][x2] != Integer.MIN_VALUE) {
// 说明这个过程曾经算过，直接从缓存中取值即可
return dp[x1][y1][x2];
}
if (x1 == m - 1 && y1 == n - 1) {
// 已经到了最右下角了
// 隐含条件：另外一个点也一定到达右下角
// 获得一份樱桃数
dp[x1][y1][x2] = matrix[x1][y1];
return matrix[x1][y1];
}
int next = -1;
// 下，下
if (x1 + 1 < m && x2 + 1 < m && matrix[x1 + 1][y1] != -1 && matrix[x2 + 1][getY2(x1, y1, x2)] != -1) {
next = Math.max(p(matrix, m, n, x1 + 1, y1, x2 + 1, dp), next);
}
// 下，右
if (x1 + 1 < m && getY2(x1, y1, x2) + 1 < n && matrix[x1 + 1][y1] != -1 && matrix[x2][getY2(x1, y1, x2) + 1] != -1) {
next = Math.max(p(matrix, m, n, x1 + 1, y1, x2, dp), next);
}
// 右，下
if (y1 + 1 < n && x2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2 + 1][getY2(x1, y1, x2)] != -1) {
next = Math.max(p(matrix, m, n, x1, y1 + 1, x2 + 1, dp), next);
}
// 右，右
if (y1 + 1 < n && getY2(x1, y1, x2) + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2][getY2(x1, y1, x2) + 1] != -1) {
next = Math.max(p(matrix, m, n, x1, y1 + 1, x2, dp), next);
}
if (next == -1) {
dp[x1][y1][x2] = -1;
return -1;
}
if (x1 == x2) {
// 到达同一个位置，只取一个值
// 将答案存入缓存
dp[x1][y1][x2] = next + matrix[x1][y1];
return dp[x1][y1][x2];
}
// 将答案存入缓存
dp[x1][y1][x2] = next + matrix[x1][y1] + matrix[x2][getY2(x1, y1, x2)];
return dp[x1][y1][x2];
}
public static int getY2(int x1, int y1, int x2) {
return x1 + y1 - x2;
}
时间复杂度O(m*n*m)，LeetCode 中直接AC。
更多
原创文章，作者：端木书台，如若转载，请注明出处：https://blog.ytso.com/270489.html