LeetCode 唯一路径问题得到错误的答案

Question

我正在一个名为 leetcode 的网站上做这个名为“唯一路径”的问题。问题是：给定一个包含 1 和 0 的二维矩阵，机器人从左上角开始，想要到达右下角。机器人只有 2 个动作：向右和向下。此外，还有障碍（由“1”表示）。机器人不能跨过障碍物。当我输入时，我的程序给出了错误的答案：0000010000000000应该输出 7，因为从左上角的方块到右下角的方块有 7 条路径。我的程序输出 2。我的猜测是，它只会一直向下并一直向右，一直向右并一直向下。但是，我不知道这种行为的原因，因为它对我来说看起来很好。谁能告诉我为什么要这样做？这是代码：class Solution {    int[][] check;    public int uniquePathsWithObstacles(int[][] grid) {        if(grid == null || grid.length == 0)            return 0;        check = new int[grid.length][grid[0].length];        return uniquePaths(grid, 0, 0);    }    private int uniquePaths(int[][] grid, int x, int y){        if(x >= grid[0].length || y >= grid.length || grid[y][x] == 1)            return 0;        else if(x == grid[0].length - 1 && y == grid.length - 1)            return 1;        else if(check[y][x] > 0)            return check[y][x];        return grid[y][x] = uniquePaths(grid, x + 1, y) + uniquePaths(grid, x, y + 1);    }}

Answer 1

对于不需要递归的“更好”实现，请从右下方开始。

如果你这样做，你只需要记住一行（或一列），所以它既更快又需要更少的内存。

例子

让我们使用这样的网格。为了不与下面的路径计数数组混淆，使用符号而不是数字来定义网格。

. . . . .

. * * . .

. . . . .

. . . . .

现在为最后一行构建一个数组，其中有多少种方法可以从那里退出。

. . . . .   last row from grid

=========

1 1 1 1 1   pathCount from each cell to the end

对其上方的行重复该操作。从右开始计算，pathCount为向右走时的pathCount + 向下走时的pathCount。

. . . . .   3rd row from grid

1 1 1 1 1   result from last row

=========

5 4 3 2 1   result for 3rd row

因为完成后我们不再需要最后一行的值，所以我们可以重用数组并替换内联值。

再重复一次。这次我们屏蔽了单元格，因此将这些单元格的 pathCount 设置为 0。

. * * . .   2nd row from grid

5 4 3 2 1   result from 3rd row

=========

5 0 0 3 1   result for 2nd row

最后：

. . . . .   1st row from grid

5 0 0 3 1   result from 2nd row

=========

9 4 4 4 1   result for 1st row

最终结果：从左上角到右下角的 9 条独特路径。

使用网格的替代格式的紧凑实现，以便于测试：

static int countPaths(String... grid) {

    int[] paths = new int[grid[0].length() + 1];

    paths[grid[0].length() - 1] = 1;

    for (int y = grid.length - 1; y >= 0; y--)

        for (int x = grid[0].length() - 1; x >= 0; x--)

            paths[x] = (grid[y].charAt(x) != '0' ? 0 : paths[x] + paths[x + 1]);

    return paths[0];

}

测试

System.out.println(countPaths("00000",

                              "01100",

                              "00000",

                              "00000")); // prints: 9

System.out.println(countPaths("000",

                              "000",

                              "000")); // prints: 6