計算迷宮中的uniq路徑數

Question

我知道在矩陣中計算路徑[0,0]到[n，n]的回溯方法。但無法通過動態編程來解決它。是否有可能沒有回溯？

你只能移動right或down

1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1
`

號路從左上到右下達到4

Answer 1

沒錯。說p（i，j）是到i，j的部分路徑的數量。如果我們使用零索引，那麼你想要的是p（n-1，n-1）。你知道的是p（0,0）= 1，如果你可以從p（i-1，j）行進到p（i，j），p（i，j） ，如果你可以從p（i，j-1）行進到p（i，j），則上面的值。

所以你用這些來填充矩陣。這幾乎就是DP：矩陣填充。一旦你弄清楚如何填寫矩陣，你就完成了。

Answer 2

static int numPath = 0; 
    // Take one sol[][] of same size as original matrix just to see your paths. 
    private static boolean MazeSolvingAllPaths(int [][] matrix, int x, int y, int[][] sol) { 


     //Base case 
     if(x == (sizeofMatrix -1) && y == (sizeofMatrix -1)) { 
      sol[x][y] = 1; 
      numPath++; // Path found so increase numPath here 
      return true; 
     } 
     if(isSafeAllPaths(matrix, x, y) == true && matrix[x][y] == 1) { 
      sol[x][y] = 1; // Mark this as solution path in solution matrix 
      // Go right and down for (x, y) 
      boolean var1 = MazeSolvingAllPaths(matrix, x, y+1, sol); 
      boolean var2 = MazeSolvingAllPaths(matrix, x+1, y, sol); 
      // If atleast one solution i found then return true 
      if(var1 || var2) {     
       return true; 
      } else { // means both var1 and var2 are false 
       sol[x][y] = 0;// unmark because i couldn't find path 
       return false; 
      } 
     } 
     return false; 
    }