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

Question

基本上我有一个类似于以下问题：

有一个以2D正方形阵列表示的草莓植物花园。每棵植物（每个元素）都有许多草莓。您从数组的左上角开始，并且只能向右或向下移动。我需要设计一种递归方法来计算通过花园的路径，然后输出产量最高的草莓。

我认为我对非常简单的递归问题有所了解，但是这个问题已经超出了我的范围。我真的不确定创建递归方法的起点或终点。

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

Answer 1

就像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和备忘录技术都是从此处使用的递归原理获得的更有效的方法。

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。