java

ux6nzvsh 于 2021-06-29 发布在 Java

关注(0)|答案(1)|浏览(269)

我被分配了一个任务，我们只能用递归方法来解决不同的问题。我对编程还相当陌生，我很难对它有足够的了解。
赋值的目标之一是计算任意给定二维整数数组中所有可能路径的最大值。基本上，这意味着当给定一个2dint数组时，我需要使用递归遍历数组中所有不同的路径（遵循一次只向下移动一个元素或向右移动一个元素的规则），并返回该路径中元素和值最高的路径值。
例如：（只是一个随机的例子，可以是任何没有特定顺序或大小的2dint数组）

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) {

        if ( (i+1) == arr.length && (j+1) == arr[0].length) { // terminates when reaches last element
        return 0;
        }else {
            if( (i+1) == arr.length) { // if the elemnt is at the last column
                return maxVal(arr, i, j) + arr[i][j-1];
            }else if ( (j+1) == arr[0].length) { // if element is at the last row
                return maxVal(arr, i, j) + arr[i-1][j];
            }else {
                return maxVal(arr, i, j) + arr[i-1][j-1];
            }
        }

    }

我一直收到一个堆栈溢出错误。任何建议都会很有帮助。

Java multidimensional-array recursion

来源：https://stackoverflow.com/questions/65481972/calculating-max-value-of-paths-inside-of-2d-int-array-using-recursion-java

1条答案

按热度按时间

osh3o9ms1#

如果您仔细观察，就会发现您正在反复调用同一个方法 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;

如果两个标记都有效，则必须递归地计算右边和下面的值，直到它最终到达路径的末尾（无效标记）
完成后，您将有两个值，这是从当前右侧和当前底部可能路径的最大和的结果，然后将当前值添加到最大值（右侧/底部）并返回它。

赞(0）回复(0）举报 2021-06-29

我来回答

java

1条答案

相关问题

热门标签

最新问答