Java - 通过2D数组的路径找到最大和

Question

Java - 通过2D数组的路径找到最大和

javaarrayspath2dsum

9

基本上，我的问题类似于这样：

有一个草莓花园，用2D方阵表示。每个植物(每个元素)都有一定数量的草莓。你从数组的左上角开始，只能向右或向下移动。我需要设计一个递归方法来计算穿过花园的路径，然后输出哪条路径可以产生最多的草莓。

我认为我理解了非常简单的递归问题，但是这个问题已经超出了我的能力范围。我不确定从何处开始创建递归方法。

如果您能提供与代码相关的任何帮助或帮助我理解这个问题背后的概念，将不胜感激。谢谢。

- user1547050

需要使用递归吗？在这里使用迭代会更简单。 - Daniel Fischer

是的，它必须是递归的。 - user1547050

好的，dasblinkenlight的答案很有效，你只需要同时跟踪向下或向右是否产生更大的数字。 - Daniel Fischer

3个回答

5

你可以使用记忆化来完成。以下是类似Java的伪代码（memo，R和C被假定为max方法可用的实例变量）。

int R = 10, C = 20;
int memo[][] = new int[R][C];
for (int r=0 ; r != R ; r++)
    for (int c = 0 ; c != C ; c++)
        memo[r][c] = -1;
int res = max(0, 0, field);

int max(int r, int c, int[][] field) {
    if (memo[r][c] != -1) return memo[r][c];
    int down = 0; right = 0;
    if (r != R) down = max(r+1, c, field);
    if (c != C) right = max(r, c+1, field);
    return memo[r][c] = (field[r][c] + Math.max(down, right));
}

- Sergey Kalinichenko

嘿，你能帮我处理一个**有点复杂的任务**吗？ - Anton Dozortsev

0

你可以使用DP表格法来解决这个问题，这样你就可以将空间从O(m*n)降低到只有O(n)。使用DP记忆化的方法，你需要一个m*n的矩阵来存储中间值。以下是我的Python代码，希望能对你有所帮助。

def max_path(field):
    dp = [sum(field[0][:i]) for i in range(1, len(field[0]) + 1)]
    for i in range(1, len(field)):
        for j in range(len(dp)):
            dp[j] = min(dp[j], dp[j - 1] if j > 0 else float('inf')) + field[i][j]
    return dp[-1]

- Jonathon.lau

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DivineWolfwood · Accepted Answer

像dasblinkenlight所说，最有效的方法是使用记忆化或动态规划技术。我倾向于使用动态规划，但在这里我将使用纯递归。

答案集中在一个基本问题的答案上：“如果我在我的领域中的第r行和第c列的正方形中，如何评估从左上角到这里的路径，使草莓的数量最大？”

关键要意识到的是，只有两种方法可以进入第r行和第c列的区块：我可以从上面进入，使用第r-1行和第c列的区块，或者我可以从侧面进入，使用第r行和第c-1列的区块。之后，您只需要确保知道您的基本情况...这意味着，从根本上讲，我的纯递归版本会是这样的：

int[][] field;    
int max(int r, int c) {
    //Base case
    if (r == 0 && c == 0) {
        return field[r][c];
    }
    //Assuming a positive number of strawberries in each plot, otherwise this needs
    //to be negative infinity
    int maxTop = -1, maxLeft = -1;
    //We can't come from the top if we're in the top row
    if (r != 0) {
        maxTop = field[r-1][c];
    }
    //Similarly, we can't come from the left if we're in the left column
    if (c != 0) {
        maxLeft = field[r][c-1];
    }
    //Take whichever gives you more and return..
    return Math.max(maxTop, maxLeft) + field[r][c];
}

请调用max(r-1, c-1)来获得你的答案。注意这里有很多低效的地方；你可以通过使用动态规划（我将在下面提供）或记忆化（已经定义好了）来获得更好的结果。但要记住，DP和记忆化技术都只是从这里使用的递归原则中简单得出的更有效的方法。

动态规划：

int maxValue(int[][] field) {
    int r = field.length;
    int c = field[0].length;
    int[][] maxValues = new int[r][c];
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (i == 0 && j == 0) {
                maxValues[i][j] = field[i][j];
            } else if (i == 0) {
                maxValues[i][j] = maxValues[i][j-1] + field[i][j];
            } else if (j == 0) {
                maxValues[i][j] = maxValues[i-1][j] + field[i][j];
            } else {
                maxValues[i][j] = Math.max(maxValues[i][j-1], maxValues[i-1][j]) + field[i][j];
            }
        }
    }
    return maxValues[r-1][c-1];
}

在这两种情况下，如果您想重新创建实际路径，请保留一个二维布尔表格，对应于“我是从上面还是左侧来的”？如果最佳草莓路径来自上方，则放置true，否则放置false。这可以让您在计算后重新跟踪路径。

请注意，这仍然是递归的原理：在每个步骤中，我们都在查看以前的结果。我们只是缓存我们以前的结果，以免浪费大量工作，并且我们正在以智能顺序攻击子问题，以便我们始终可以解决它们。有关动态规划的更多信息，请参见Wikipedia。