为什么我的代码在使用 2d 数组列表时给出错误答案，而在使用 2d 数组时给出错误答案？

Question

这是DP问题， 给定一个带有障碍物的“N”*“M”迷宫，计算并返回从左上角单元格到达右下单元格的唯一路径的数量。如果给定迷宫中的单元格是阻塞或死胡同，则其值为“-1”，否则为 0。从给定单元格，我们可以移动到单元格 (i+1, j) 和 (i, j)仅+1)。由于答案可能很大，因此将其打印为 10^9 + 7 模。 例如：

考虑下面的迷宫： 0 0 0 0 -1 0 0 0 0

有两种方法可以到达左下角 -

(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3) (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)

因此上述测试用例的答案是2。

**这是我使用二维数组的解决方案。 **

导入java.util.*;

公开课解决方案{

public static int f(int i, int j, ArrayList<ArrayList<Integer>> mat,int [][]dp){

    if(i == 0 && j == 0)
    return 1;
  if((i < 0) || j < 0 || (mat.get(i).get(j)) == -1)
    return 0;
    if(dp[i][j] != -1)
    return dp[i][j];
   
   
    return dp[i][j] =  f(i-1,j,mat,dp)%1000000007+f(i,j-1,mat,dp)%1000000007;
   

}

static int mazeObstacles(int n, int m, ArrayList<ArrayList<Integer>> mat) {
    int dp[][] = new int[n][m];
    
    // Initialize the dp array with -1
    for (int row[] : dp)
        Arrays.fill(row, -1);
   return f(n-1,m-1,mat,dp)%1000000007;
  
}

}

这是我使用 2d ArrayList 的解决方案：

导入java.util.*;

公开课解决方案{

public static int f(int i, int j, ArrayList<ArrayList<Integer>> mat, ArrayList<ArrayList<Integer>> dp){

    if(i == 0 && j == 0)
    return 1;
  if((i < 0) || j < 0 || (mat.get(i).get(j)) == -1)
    return 0;
    if(dp.get(i).get(j) != -1)
    return dp.get(i).get(j);
   
   
    return dp.get(i).set(j , f(i-1,j,mat,dp)%1000000007+f(i,j-1,mat,dp)%1000000007);
   

}

static int mazeObstacles(int n, int m, ArrayList<ArrayList<Integer>> mat) {
    // Write your code here.
    ArrayList<ArrayList<Integer>> dp = new ArrayList<>();
     for (int i = 0; i < n; i++) {
        ArrayList<Integer> row = new ArrayList<>();
        for (int j = 0; j < m; j++) {
            row.add(-1);  // Add 0 to each column in the row
        }
        dp.add(row);  // Add the row to the 2D ArrayList
    }
   return f(n-1,m-1,mat,dp)%1000000007;
  
}

}

我尝试最初使用 -1 初始化 2d arrayList，并基于此累积我的 DP 数组。

请帮助我使用 2d ArrayList 时出错的地方。

Answer 1

您在

ArrayList

解决方案中返回了错误的项目。 将您的最后一条语句更改为以下内容。 Set 返回被替换的前一个元素，而不是当前元素。

dp.get(i).set(j, f(i - 1, j, mat, dp) % 1000000007
                    + f(i, j - 1, mat, dp) % 1000000007);
return dp.get(i).get(j);