为什么我的代码在使用 2d ArrayList 时给出错误答案，而在使用 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。

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

import java.util.*;

public class Solution {

    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 的解决方案：

import java.util.*;

public class Solution {

    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

返回被替换的前一个元素，而不是新元素。

来自 JavaDoc。

Specified by:
    set in interface List<E>
Overrides:
    set in class AbstractList<E>
Parameters:
    index - index of the element to replace
    element - element to be stored at the specified position
Returns:
    the element previously at the specified position

将您最后的陈述更改为以下内容。

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);

当我进行更改时，两种解决方案都使用您的初始迷宫数据返回

2

的值。