Java - 通过二维数组的路径中的最大总和

Question

基本上我遇到的问题与此类似:

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

我想我已经理解了非常简单的递归问题，但是这个问题让我难以理解。就创建递归方法而言，我不确定从哪里开始或去哪里。

非常感谢任何与代码相关的帮助或帮助我理解此问题背后的概念。谢谢。

Answer 1

正如 dasblinkenlight 所说，最有效的方法是使用内存或动态编程技术。我倾向于更喜欢动态规划，但我将在这里使用纯递归。

答案围绕一个基本问题的答案:“如果我在我的田地的第 r 行和第 c 列的正方形中，我如何评估从左上角到这里的路径，使得草莓的数量最大化了吗？”

要意识到的关键是，只有两种方法可以进入 r 行和 c 列的绘图:要么我可以从上面到达那里，使用 r-1 行和 column 中的绘图，或者我可以到达那里从侧面看，使用 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];
}

在这两种情况下，如果您想重新创建实际路径，只需保留一个与“我是从上面还是从左边来”相对应的二维 boolean 值表？如果最多的草莓路径来自上面，则为true，否则为false。这可以让您在计算后追溯补丁。

请注意，这在原则上仍然是递归的:在每一步中，我们都会回顾之前的结果。我们只是碰巧缓存了之前的结果，这样我们就不会浪费大量的工作，而且我们正在以智能顺序攻击子问题，这样我们总能解决它们。有关动态规划的更多信息，请参阅 Wikipedia .