计算迷宫中的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; 
    }