Java – 通过2D数组的路径的最大总和
基本上我有一个与此类似的问题：
草坪植物花园由2D方形arrays代表。 每株植物（每种元素）都有许多草莓。 从arrays的左上角开始，您只能向右或向下移动。 我需要设计一个递归方法来计算通过花园的路径，然后输出哪一个产生最多的草莓。
我想我对真正非常简单的递归问题有所了解，但这个问题已经过去了。 就创建递归方法而言，我不确定从哪里开始或去哪里。
任何与代码相关的帮助或帮助我理解这个问题背后的概念都非常感谢。 谢谢。
像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 。
你可以使用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)); }
您可以使用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]