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

Question

我正在一个名为 leetcode 的网站上做这个名为“唯一路径”的问题。问题是：给定一个包含 1 和 0 的二维矩阵，机器人从左上角开始，想要到达右下角。机器人只有 2 个动作：向右和向下。此外，还有障碍（由“1”表示）。机器人不能跨过障碍物。当我输入时，我的程序给出了错误的答案：

0000

0100

0000

0000

应该输出 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 grid1 1 1 1 1   result from last row=========5 4 3 2 1   result for 3rd row因为完成后我们不再需要最后一行的值，所以我们可以重用数组并替换内联值。再重复一次。这次我们屏蔽了单元格，因此将这些单元格的 pathCount 设置为 0。. * * . .   2nd row from grid5 4 3 2 1   result from 3rd row=========5 0 0 3 1   result for 2nd row最后：. . . . .   1st row from grid5 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: 9System.out.println(countPaths("000",                              "000",                              "000")); // prints: 6