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

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

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

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

例

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

. . . . .. * * . .. . . . .. . . . .

现在为最后一行建立一个数组，其中有几种方法可以从那里获得出口。

. . . . .   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