我有一个二维数组,我需要找到可以通过左下并且仅从上到右直到到达终点 收集的最大和路径。我已经在 Java 上完成了(任务非常类似于 Project Euler: Problem 81 ):
static int maxSumPath(int[][] data) {
final int length = data.length;
final int[][] sumArr = new int[length][length];
for (int row = length - 1; row >= 0; row--) {
for (int col = 0; col < length; col++) {
if (row == length - 1 && col == 0) {
sumArr[row][col] = data[row][col];
} else if (row == length - 1) {
sumArr[row][col] = sumArr[row][col - 1] + data[row][col];
} else if (col == 0) {
sumArr[row][col] = sumArr[row + 1][col] + data[row][col];
} else {
sumArr[row][col] = Math.max(sumArr[row][col - 1], sumArr[row + 1][col]) + data[row][col];
}
}
}
return sumArr[0][length - 1];
}
例子
3, 0, 2
2, 0, 0
0, 3, 0
结果7。
但现在我需要实现机会将该数组的任何值加倍以获得更好的分数,我只能做两次并且只能将某个值加倍一次。
示例(在这个矩阵中带有*
的数字必须加倍)
3*, 0, 2
2*, 0, 0
0*, 3, 0
结果12。
最佳答案
您可以通过向二维数组添加第三个维度来解决此问题,该数组恰好有三层:
final int[][][] sumArr = new int[3][length][length]
- 第 0 层表示无需将任何元素加倍即可获得的最佳总和
- 第一层表示仅将一个数字加倍可以获得的最佳总和
- 第二层表示将两个数字加倍可以获得的最佳总和
该算法是对现有算法的简单扩展,只是现在您需要在 if
条件的每个分支中设置三个部分和。
下面是你根据上面修改的代码:
static int maxSumPath(int[][] data) {
final int length = data.length;
final int[][][] sumArr = new int[3][length][length];
for (int row = length - 1; row >= 0; row--) {
for (int col = 0; col < length; col++) {
int val = data[row][col];
int val2 = data[row][col] * 2;
if (row == length - 1 && col == 0) {
sumArr[0][row][col] = val;
sumArr[1][row][col] = val2;
} else if (row == length - 1) {
sumArr[0][row][col] = sumArr[0][row][col - 1] + val;
sumArr[1][row][col] = Math.max(
sumArr[1][row][col - 1] + val
, sumArr[0][row][col - 1] + val2
);
sumArr[2][row][col] = Math.max(
sumArr[1][row][col - 1] + val2
, sumArr[2][row][col - 1] + val
);
} else if (col == 0) {
sumArr[0][row][col] = sumArr[0][row + 1][col] + val;
sumArr[1][row][col] = Math.max(
sumArr[0][row + 1][col] + val2
, sumArr[1][row + 1][col] + val
);
sumArr[2][row][col] = Math.max(
sumArr[1][row + 1][col] + val2
, sumArr[2][row + 1][col] + val
);
} else {
sumArr[0][row][col] = Math.max(
sumArr[0][row][col - 1], sumArr[0][row + 1][col]
) + data[row][col];
sumArr[1][row][col] = Math.max(
Math.max(sumArr[0][row][col - 1], sumArr[0][row + 1][col]) + val2
, Math.max(sumArr[1][row][col - 1], sumArr[1][row + 1][col]) + val
);
sumArr[2][row][col] = Math.max(
Math.max(sumArr[1][row][col - 1], sumArr[1][row + 1][col])+val2
, Math.max(sumArr[2][row][col - 1], sumArr[2][row + 1][col])+val
);
}
}
}
return sumArr[2][0][length - 1];
}
关于java - 二维数组中的最大和路径+两个值加倍以获得更好的分数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42706957/