我正在一個名為 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); }}
1 回答
胡子哥哥
TA貢獻1825條經驗 獲得超6個贊
對于不需要遞歸的“更好”實現，請從右下方開始。
如果你這樣做，你只需要記住一行（或一列），所以它既更快又需要更少的內存。
例子
讓我們使用這樣的網格。為了不與下面的路徑計數數組混淆，使用符號而不是數字來定義網格。
. . . . .
. * * . .
. . . . .
. . . . .
現在為最后一行構建一個數組，其中有多少種方法可以從那里退出。
. . . . . 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
添加回答
舉報
0/150
提交
取消