在网格中寻找最优路径

Question

背景今天去面试了，问了下面的问题

给你一个网格。

  int [][] grid =
                {
                {0,0,0,2,5},
                {0,0,0,1,5},
                {0,1,1,1,1},
                {2,0,0,0,0}
                };

你从网格的左下角开始。你只能上和右。这个想法是到达右上角。你要走能让你获得最大价值的道路。

The output for the above would be 16

我的解决方案

public static int getPathMaxSum(int [][] grid){
    int row = grid.length-1;
    int col = 0;
    int currentSum = grid[row][col];
    return getMax(grid,currentSum,row,col);
}

public static int getMax(int [][] grid,int sum,int row,int col){
    if((isTopRight(grid,row,col)) || (!isValid(grid,row,col))){
        return sum;
    }else{
        sum = sum + grid[row][col];
        return Math.max(getMax(grid,sum,row-1,col),getMax(grid,sum,row,col+1));
    }
}

public static boolean isTopRight(int [][] grid, int row, int col){
    return row == 0 && col == grid[row].length-1;
}

public static boolean isValid(int [][] grid, int row, int col){
    return (row >= 0 &&  row < grid.length) && (col >= 0 && col < grid[row].length);
}

我正在尝试递归地解决这个问题。我认为我在每个位置都有 2 个可能的选择，我想获得两个选择中的最大值，但由于某种原因我无法获得正确的输出。

我有两个辅助函数来检查我的位置是否在网格内有效，以及我是否点击了右上角，如果我点击了我的基本情况。

我很乐意提供意见，看看我哪里出错了。

Answer 1

EDIT：对您代码的编辑版本的回答

您的新解决方案存在问题：

int currentSum = grid[row][col]; 和 sum = sum + grid[row][col];

总和用左下角的值初始化，在 getMax() 的初始调用中再次添加相同的值。这不是应该的样子。求和从0开始，加起来就是getMax().
if((isTopRight(grid,row,col)) || (!isValid(grid,row,col))) 然后 return sum;

对于无效位置，这将起作用（请参阅我的代码下方的限制），但不适用于右上角（因为我们尚未添加角的值）。因此，将两个条件分开，仅 return 直接位于无效位置。在任何其他位置，首先添加值，然后，如果您达到“目标”，return 总和。否则return“向右”和“向上”的最大值（现在递归调用正确）。

解决这些问题并实施您的示例，我得出以下代码：

public class Pathfinder {

    public static void main(String... args) {
        int [][] grid = {
            {0,0,0,2,5},
            {0,0,0,1,5},
            {0,1,1,1,1},
            {2,0,0,0,0}
        };
        
        System.out.println(getPathMaxSum(grid));
    }

    public static int getPathMaxSum(int[][] grid) {
        int row = grid.length - 1;
        int col = 0;
        
        return getMax(grid, 0, row, col);
    }

    public static int getMax(int[][] grid, int sum, int row, int col) {
        if(!isValid(grid, row, col))
            return sum;
        
        sum = sum + grid[row][col];
        
        if(isTopRight(grid, row, col))
            return sum;
        
        return Math.max(getMax(grid, sum, row - 1, col), getMax(grid, sum, row, col + 1));
    }

    public static boolean isTopRight(int[][] grid, int row, int col) {
        return row == 0 && col == grid[row].length - 1;
    }

    public static boolean isValid(int[][] grid, int row, int col) {
        return (row >= 0 &&  row < grid.length) && (col >= 0 && col < grid[row].length);
    }
}

请注意，如果所有条目都是非消极的。无论如何，可以以这种方式操纵具有负条目的网格，该算法将找到最佳路径，并且可以轻松地将解决方案“翻译”回原始网格（只需从每个条目中减去最小值）。

原始代码的答案

我发现您的代码存在多个问题：

isValid(grid,row+1,col) 和 sum1 = grid[row+1][col];

您正在尝试添加 1 到该行，但您从 int row = grid.length-1; 开始（正确地）。添加 1 会给你一个无效的位置，因此第一个分支将永远不会被执行。相反，您需要从该行中减去 1 以“上升”。
sum = sum + Math.max(sum1,sum2);

这会改变 sum，但您看不到您移动的方向。然后直接...
getMax(grid,sum,row+1,col); 和 getMax(grid,sum,row,col+1);

...您使用新的最大总和进行递归调用，但是从两个点进行。要获得正确的解决方案，您应该用值来调用它们，它们的方向代表。另请注意，此处 row+1 也需要替换为 row-1。
return sum;

您现在 return 这个最大总和，但完全忽略了您的递归调用的 return。您应该比较他们的 return 和 return 自己，两者的价值更高。
回溯与动态规划

您的算法应该可以正常工作，并且足以解决问题的小实例，但不适用于较大的问题（因为它会为每一步进行 2 次递归调用，而您有 2*(n-1) 步..导致指数运行时间）。二次运行时的另一种方法是向后遍历该字段并通过仅向右或向上查看一个字段并将当前字段的值添加到该字段的最大值来选择最佳方法。就从右上角开始往左走，从右到左一行一行。

Answer 2

您的方法中不需要 sum 参数。

我假设您已经了解如何使用自上而下的递归方法解决此问题。但再次为了完整起见，基本公式是：

您从位于 row 的单元格开始，col 获取其值，然后向上 (row-1, col) 或向右 (row, col+1).

查找

所以结果将是：

grid[row][col] + Math.max( getMax( row-1, col, grid ), getMax( row, col+1, grid ) )

基础条件：

a) 如果它在右上角，即目的地，你不需要递归你只是 return 该单元格的值。

b) 如果它是一个无效的单元格，就像您在 isValid 方法中所写的那样，您需要 return Integer.MIN_VALUE 因为您的其他单元格中可能有负值并且您希望它们最大。

所以你的 getMax 函数需要是：

public static int getMax(int [][] grid,int row,int col){
    if (isTopRight(grid,row,col)) {
       return grid[row][col];
    } else if (!isValid(grid,row,col)){
        return Integer.MIN_VALUE;
    } else {
        return grid[row][col] + Math.max(getMax(grid,row-1,col),getMax(grid,row,col+1));
    }
}

你可以看到工作示例here

在网格中寻找最优路径

Finding the optimal path in a grid

java

algorithm

recursion

dynamic-programming

backtracking