我在一个名为leetcode的网站上遇到了称为“唯一路径”的问题。问题是：给定具有1s和0s的2D矩阵，机器人将从左上角开始，并希望到达右下角。机器人只有两个动作：向右和向下。此外，还有障碍（以“ 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); } }
对于不需要递归的“更好”的实现，请从右下角开始。
如果这样做，您只需要记住一行（或一列），这样既更快又需要更少的内存。
例
让我们使用这样的网格。为了不与下面的路径计数数组混淆，请使用符号代替数字来定义网格。
. . . . . . * * . . . . . . . . . . . .
现在为最后一行建立一个数组，其中有几种方法可以从那里获得出口。
. . . . . 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
