Java - 通过二维数组的路径中的最大总和 [英] Java - Maximum sum in path through a 2D array

查看:26
本文介绍了Java - 通过二维数组的路径中的最大总和的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

Basically I have a problem that goes something similar to this:

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

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.

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

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.

推荐答案

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

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.

答案围绕着一个基本问题的答案:如果我在我的田地的第 r 行和第 c 列的正方形中,我如何评估从左上角到这里的路径,使得草莓的数量最大化了吗?"

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 列的绘图:要么我可以从上方到达那里,使用第 r-1 行和 c 列的绘图,要么我可以到达那里从侧面,使用第 r 行和 c-1 列中的绘图.在那之后,你只需要确保你知道你的基本情况......这意味着,从根本上说,我的纯递归版本将是这样的:

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:

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 和记忆技术都是来自此处使用的递归原则的更有效的方法.

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.

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.

这篇关于Java - 通过二维数组的路径中的最大总和的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆