9

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

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

我想我对非常简单的递归问题有所了解，但是这个问题已经超出了我的想象。我不确定从哪里开始或从哪里开始创建递归方法。

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

4

3 回答 3

15

就像 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];
}

在这两种情况下，如果您想重新创建实际路径，只需保留一个与“我是从上方还是左侧来”相对应的 2D 布尔值表？如果最草莓路径来自上方，则设为 true，否则设为 false。这可以让您在计算后回溯补丁。

请注意，原则上这仍然是递归的：在每一步，我们都在回顾之前的结果。我们只是碰巧缓存了我们之前的结果，这样我们就不会浪费大量的工作，而且我们正在以一种智能的顺序攻击子问题，以便我们总能解决它们。有关动态编程的更多信息，请参阅Wikipedia。

于 2012-07-23T23:00:08.913 回答
5

您可以使用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-23T22:21:15.297 回答
0

您可以使用 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-15T22:37:15.530 回答