2D数组中的java最大求和路径+两个值以获得更好的分数

Question

我有一个2d数组，我需要找到可以由左下角收集的最大和路径，并且只能从上到右，直到到达终点。我在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

但现在我需要实现opportunity，将该数组的任何值加倍，以获得更好的分数，我只能执行两次，并且只能将特定值加倍一次

示例（在此矩阵中，带*的数字必须加倍）

3*, 0, 2

2*, 0, 0

0*, 3, 0

结果12

Answer 1

您可以通过向二维阵列中添加第三维来解决此问题，其中正好有三层：

final int[][][] sumArr = new int[3][length][length]

• 零层表示在不加倍任何元素的情况下可以得到的最佳总和
• 第一层代表的是仅将一个数字加倍所能得到的最佳总和
• 第二层代表两个数字加倍所能得到的最佳总和

该算法是对已有算法的简单扩展，只是现在需要在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];
}

Demo