java - 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。
但现在我需要实现一个将数组的任何值加倍的机会，以获得更好的分数，我只能做到两次，将某个值加倍一次。
示例（在此矩阵中，*的数字必须加倍）
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];
}

Demo