爪哇 - 通过二维数组

路径最大总和基本上我有去类似于这样一个问题：爪哇 - 通过二维数组

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

我想我真的很简单的递归问题的理解，但这个问题已经超出了我的头。我并不确定从哪里开始或到哪里去创建一个递归方法。

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

来源

2012-07-23 user1547050

它是否必须递归？迭代在这里会更简单。 – 2012-07-23 22:17:34

是的，它必须是递归的。 – user1547050 2012-07-23 22:42:57

那么，dasblinkenlight的答案效果很好，你只需要跟踪是否下降或者右边会产生更大的数字。 – 2012-07-23 22:47:58

像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）得到你的答案。注意这里有很多低效率;你会通过使用动态编程（我将在下面提供）或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]; 
}

在这两种情况下，如果要重新创建实际的路径，只是不停地与对应的布尔值二维表“难道我来自上方或左边的”？如果最多的草莓路径来自上面，则变为真实，否则为假。这可以让您在计算后追溯修补程序。

请注意，这仍然是主要的递归：在每一步，我们回顾我们以前的结果。我们只是缓存了以前的结果，所以我们不会浪费大量的工作，而且我们正在以一个明智的顺序攻击子问题，以便我们可以随时解决它们。有关动态编程的更多信息，请参阅Wikipedia。

来源

2012-07-23 23:00:08 DivineWolfwood

你可能意思是'return maxValues [r-1] [c-1];' – Quixotic 2012-12-08 16:28:47

哎呀，谢谢！ – DivineWolfwood 2014-03-13 02:24:53

嗨DivineWolfwood，你的例子很有趣。但是，我想看看左右两边是什么？ – Doro 2014-04-05 17:07:48

你可以使用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)); 
}

来源

2012-07-23 22:21:15 dasblinkenlight

嘿，你可以帮助我，但一个** [有点复杂的任务]（http://stackoverflow.com/q/42706957/2650174）**。 – 2017-03-09 23:12:17

您可以使用DP制表方法解决此问题，您可以使用该制表方法将空间从O（m * n）节省到O（n）。使用DP记忆，您需要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]

来源

2018-02-15 22:37:15

爪哇 - 通过二维数组

回答

相关问题