0

我被分配了一项任务，我们只能使用递归方法来解决给我们的不同问题。我对编程还很陌生，我很难理解它。

作业的目标之一是计算任何给定二维整数数组中所有可能路径的最大值。基本上这意味着当给定一个 2D int 数组时，我需要使用递归遍历数组中的所有不同路径（遵守一次仅向下移动一个元素或向右移动一个元素的规则）并返回该路径中元素总和值最高的路径的值。

例如：（只是一个随机示例，可以是没有特定顺序或大小的任何 2D int 数组）

int[][] arr = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}};

输出应该是：'48' (1 + 5 + 9 + 10 + 11 + 12)

这就是我到目前为止所拥有的（但我有一种感觉我很遥远）：

public static int maxVal(int[][] arr) {
    return maxVal(arr, 0, 0);
} // end of method

// Returns the value of the maximal path in the
// given 2D array, starting at location (i,j)
private static int maxVal(int[][] arr, int i, int j) {
    // terminates when reaches last element
    if ((i + 1) == arr.length && (j + 1) == arr[0].length) { 
        return 0;
    } else {
        // if the elemnt is at the last column
        if ((i + 1) == arr.length) { 
            return maxVal(arr, i, j) + arr[i][j - 1];
        // if element is at the last row
        } else if ((j + 1) == arr[0].length) { 
            return maxVal(arr, i, j) + arr[i - 1][j];
        } else {
            return maxVal(arr, i, j) + arr[i - 1][j - 1];
        }
    }
}

我不断得到一个StackOverFlowError. 任何建议都会非常有帮助。

4

1 回答 1

2

如果您仔细观察，您会发现您一遍又一遍地调用相同的方法return maxVal(arr, i, j)，这将导致 SOF 异常，因为将有 infi 递归调用，因为没有任何变化会触发基本情况。

相反，您应该返回添加到右侧/底部最大值的当前值。

private static int maxVal(int[][] arr, int i, int j)
    {
        if (i >= arr.length || i < 0 || j >= arr[i].length || j < 0) return 0;
        int right = maxVal(arr, i, j + 1);
        int bottom = maxVal(arr, i + 1, j);
        return arr[i][j] + Math.max(right, bottom);
    }

尽量不要迷失在递归兔子洞中，而是设置正确的基本情况，一旦你到达无效的 i 或 j，你应该只返回 0（当前路径的结尾）

if (i >= arr.length || i < 0 || j >= arr[i].length || j < 0) return 0;

如果两个索引都有效，则您将不得不递归计算右值和底部值，直到它最终到达路径的末尾（无效的索引）

完成后，您将有两个值，即当前右侧和当前底部的可能路径的最大总和的结果，然后将当前值添加到最大值（右侧/底部）并返回它。

于 2020-12-28T18:28:41.253 回答