java - 二维数组中的最大和路径+两个值加倍以获得更好的分数

Question

我有一个二维数组，我需要找到可以通过左下并且仅从上到右直到到达终点 收集的最大和路径。我已经在 J​​ava 上完成了(任务非常类似于 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。

Answer 1

您可以通过向二维数组添加第三个维度来解决此问题，该数组恰好有三层:

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];
}

Demo