Java - 通过二维数组的路径中的最大总和
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11621337/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java - Maximum sum in path through a 2D array
提问by user1547050
Basically I have a problem that goes something similar to this:
基本上我有一个类似的问题：
There is a garden of strawberry plants represented by a 2D, square array. Each plant(each element) has a number of strawberries. You start at the top left corner of the array, and you can only move to the right or down. I need to design a recursive method to calculate the paths through the garden and then output which one yields the most strawberries.
有一个由 2D 方阵表示的草莓植物园。每个植物（每个元素）都有一些草莓。你从数组的左上角开始，你只能向右或向下移动。我需要设计一种递归方法来计算穿过花园的路径，然后输出哪个产生最多的草莓。
I think I have an understanding of really really simple recursion problems, but this problem has gone way over my head. I'm not really sure where to start or where to go as far as creating a recursive method.
我想我对非常简单的递归问题有一定的了解，但是这个问题已经超出了我的脑海。就创建递归方法而言，我不确定从哪里开始或去哪里。
Any help related to the code or helping me understand the concept behind this problem is greatly appreciated. Thanks.
非常感谢与代码相关的任何帮助或帮助我理解此问题背后的概念。谢谢。
回答by DivineWolfwood
Like dasblinkenlight said, the most efficient way to do this is using a memoization or dynamic programming technique. I tend to prefer dynamic programming, but I'll use pure recursion here.
就像 dasblinkenlight 所说，最有效的方法是使用记忆或动态编程技术。我倾向于使用动态编程，但我将在这里使用纯递归。
The answer centers around the answer to one fundamental question: "If I'm in the square in row r and column c on my field, how can I evaluate the path from the top left to here such that the number of strawberries is maximized?"
答案围绕一个基本问题的答案展开：“如果我在我的田地中第 r 行和 c 列的正方形中，我如何评估从左上角到此处的路径以使草莓数量最大化？ ”
The key to realize is that there's only two ways to get in the plot in row r and column c: either I can get there from above, using the plot in row r-1 and column c, or I can get there from the side, using the plot in row r and column c-1. After that, you just need to make sure you know your base cases...which means, fundamentally, my purely recursive version would be something like:
实现的关键是只有两种方法可以进入第 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];
}
Call max(r-1, c-1) to get your answer. Notice there's a lot of inefficiency here; you'll do much better by using dynamic programming (which I'll provide below) or memoization (which has already been defined). The thing to remember, though, is that both the DP and memoization techniques are simply more efficient ways that come from the recursive principles used here.
致电 max(r-1, c-1) 以获得答案。请注意，这里存在很多低效率；通过使用动态编程（我将在下面提供）或记忆化（已经定义），您会做得更好。不过，要记住的是，DP 和记忆技术都是来自这里使用的递归原则的更有效的方法。
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];
}
In both cases, if you want to recreate the actual path, just keep a 2D table of booleans that corresponds with "Did I come from above or to the left"? If the most strawberry path comes from above, put true, otherwise put false. That can allow you to retrace the patch after the calculation.
在这两种情况下，如果您想重新创建实际路径，只需保留一个与“我来自上方还是左侧”相对应的二维布尔值表？如果最草莓的路径来自上方，则为真，否则为假。这可以让您在计算后回溯补丁。
Notice that this is still recursive in principal: at each step, we're looking back at our previous results. We just happen to be caching our previous results so we don't waste a bunch of work, and we're attacking the subproblems in an intelligent order so that we can always solve them. For more on dynamic programming, see Wikipedia.
请注意，这在原则上仍然是递归的：在每一步，我们都在回顾我们之前的结果。我们只是碰巧缓存了我们之前的结果，所以我们不会浪费大量工作，而且我们正在以智能顺序解决子问题，以便我们始终可以解决它们。有关动态规划的更多信息，请参阅Wikipedia。
回答by dasblinkenlight
You can do it using memoization. Here is Java-like pseudodoce (memo, R, and Care assumed to be instance variables available to the maxmethod).
您可以使用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));
}
回答by Jonathon.lau
You can solve this with DP tabulation method, with which you can save space from O(m*n) to just O(n). With DP Memorization, you need m*n matrix to store intermediate values. Following is my Python code. Hope it can help.
您可以使用 DP 制表方法解决此问题，使用该方法可以将空间从 O(m*n) 节省到 O(n)。使用 DP Memorization，您需要 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]
