在网格中寻找最佳路径

Question

背景 我今天接受了一次采访，被问到以下问题。给你一个网格。  int [][] grid =                {                {0,0,0,2,5},                {0,0,0,1,5},                {0,1,1,1,1},                {2,0,0,0,0}                };您从网格的左下角开始。你只能向上和向右。这个想法是到达右上角。你要走一条能给你带来最大价值的道路。上面的输出是 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

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）如果它位于右上角，即目的地，则无需递归，只需返回该单元格处的值即可。

b）如果它是一个无效的单元格，就像您在方法中编写的那样isValid，您需要返回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));

    }

}

Answer 2

编辑：回答代码的编辑版本

新解决方案存在的问题：

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

   总和使用左下角的值进行初始化，并在初始调用中getMax()再次添加相同的值。这不应该是这样的。总和从 0 开始，加法将通过 完成getMax()。

2. if((isTopRight(grid,row,col)) || (!isValid(grid,row,col)))然后return sum;

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

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

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);

    }

}

请注意，如果所有条目均为非负数，则此版本将适用于任何网格（只要堆栈足够大并且我们不处理太大的数字，例如我们不会得到任何整数溢出）。无论如何，可以通过以下方式操作具有负条目的网格，即通过该算法找到最佳路径，并且可以轻松地将解决方案“翻译”回原始网格（只需从每个条目中减去最小值）。

原始代码的答案

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

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

   您正在尝试向该行添加int row = grid.length-1;1，但您（正确地）从 开始。加 1 会给你一个无效的位置，因此第一个分支将永远不会被执行。相反，您需要从该行中减去1 才能“向上”。

2. sum = sum + Math.max(sum1,sum2);

   这会改变sum，但你看不到你移动的方向。然后紧接着...

3. getMax(grid,sum,row+1,col);和getMax(grid,sum,row,col+1);

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

4. return sum;

   您现在返回这个最大总和，但完全忽略递归调用的返回。相反，您应该比较它们的回报并为自己回报两者的较高价值。

5. 回溯法与动态规划

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