java - 递归方法查找矩阵中的路径数

Question

我编写了一个方法来计算从二维数组中的给定单元格到给定目标单元格的路径数，但由于某种原因它返回了错误的答案，有什么想法吗？

   private static int numParths(int [][] mat, int x1, int y1, int x2, int y2)
    {
        if(x1<0  ||  x1 >mat.length-1 || y1<0  ||  y1>mat.length-1)
          return 0;


        if(x1 == x2 && y1 == y2){
        System.out.println("1"); 
          return 1;
        }


        if(mat[x1][y1]==-1)
          return 0;

          mat[x1][y1]=-1;
          return numParths(mat, x1, y1+1, x2, y2) + numParths(mat, x1-1, y1, x2, y2) + numParths(mat, x1+1, y1, x2, y2) + numParths(mat, x1, y1-1, x2, y2);
    }

    public static void main (String[]args){
        int [][] mat={{1,2,3,4},{1,2,3,4},{1,2,3,4},{1,2,3,4}};
        System.out.println(numParths(mat, 0,1,2,3));
    }

Answer 1

这类问题可以使用递归和一些“看起来很干净”的代码来解决。但是，最好先在一般递归之上构建一个解决方案，然后看看是否可以使用动态编程来提高效率。 关于这个特定问题，我们可以通过将其存储在变量中来重新使用已经计算出的信息(从引用点到目标点的路径数)。另一个具有相似维度的矩阵在这里对我们有好处(因为我们可能不想更改输入矩阵)。

以下是几个解决方案:

1. 普通递归方法(在效率方面不推荐)

   //Call to a recursive method numPathsRecursive. There is no need of passing matrix array, just source and destination points are sufficient.
   
   int numPaths(int[][] matrix, int x, int y, int X, int Y){
      return numPathsRecursive(x,y,X,Y); 
   }
   
   
   int numPathsRecursive(int x, int y, int X, int Y){// x and y are Source co ordinates; X and Y are destination co ordinates
       if (x==X && y==Y){
           return 1;
       }
       else if (x>X || y>Y){//Boundary Conditions possible (Right part of Matrix & Bottom part of Matrix)
           return 0;
       }
      return numPathsRecursive(x+1,y,X,Y) + numPathsRecursive(x,y+1,X,Y);
   }
   

2. 基于动态编程的方法(我们基本上建立在上述递归方法之上)

   int numPaths(int[][] matrix, int x, int y, int X, int Y){
      int countMatrixRows = X-x+1;
      int countMatrixColumns = Y-y+1;
      int[][] countMatrix = new int[countMatrixRows][countMatrixColumns];// initialising count matrix which stores number of paths from each point to the end point of the count Matrix (i.e., destination of original matrix)
       for (int i=0;i<countMatrixRows;i++){//Initialisation of countMatrix with -1s
           for (int j=0;j<countMatrixColumns;j++){
               countMatrix[i][j]=-1;
           }
       }
       countMatrix[countMatrixRows-1][countMatrixColumns-1]=1; //Setting destination cell value as 1. (indicating there's one path to itself)
       return numPathsDP(countMatrix,0,0,countMatrixRows-1,countMatrixColumns-1); //Call to numPathsDP. Now the original problem boils down to finding path from 0,0 of countMatrix to countMatrixRows-1,countMatrixColumns-1
   }
   
   int numPathsDP(int[][] countMatrix, int x, int y, int X, int Y){
       if (x>X || y>Y){
           return 0;
       }
       if (countMatrix[x][y]==-1){
           countMatrix[x][y]=numPathsDP(countMatrix,x+1,y,X,Y)+numPathsDP(countMatrix,x,y+1,X,Y); //It's indeed a recursive function but we are storing the result value in the same 2d array
       }
       return countMatrix[x][y]; // It will return 1 when destination cell is reached the first time. The same returned value will be used to add up when called from other cells (See above line)
   }
   

假设:

1. 你只允许在你的右边和底部遍历，如果有其他可能的路径，你只需要在索引上调用适当的操作方法即可。例如，如果也允许对角线，则需要添加额外的方法调用

   numPathsDP(countMatrix,x+1,y+1,X,Y)
   

总结一下。即，总和为

 countMatrix[x][y]=numPathsDP(countMatrix,x+1,y,X,Y)+numPathsDP(countMatrix,x,y+1,X,Y)+numPathsDP(countMatrix,x+1,y+1,X,Y) 

在 DP 解决方案中。

1. 目标单元格可从源单元格到达，并且源单元格和目标单元格都包含在原始矩阵中(基于矩阵的维度)