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

Question

基本上我有一个与此类似的问题:

草莓植物花园由2D方形阵列代表.每株植物(每种元素)都有许多草莓.从阵列的左上角开始,您只能向右或向下移动.我需要设计一个递归方法来计算通过花园的路径,然后输出哪一个产生最多的草莓.

我想我对真正非常简单的递归问题有所了解,但是这个问题已经过去了.就创建递归方法而言,我不确定从哪里开始或去哪里.

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

Answer 1

像dasblinkenlight所说,最有效的方法是使用memoization或动态编程技术.我倾向于喜欢动态编程,但我会在这里使用纯递归.

答案围绕着一个基本问题的答案:"如果我在我的田地的第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)得到你的答案.注意这里有很多低效率; 通过使用动态编程(我将在下面提供)或memoization(已经定义),你会做得更好.但要记住的是,DP和memoization技术都是来自此处使用的递归原理的更有效的方法.

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.

Answer 2

您可以使用memoization来做到这一点。这是类 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));
}