使用二维ArrayList的DP迷宫路径代码出错，二维数组版本正常求排查

给定一个N*M的带障碍迷宫，统计并返回从左上角单元格到右下角单元格的唯一路径数量。迷宫中值为-1的单元格是障碍物或死路，其余为0。每次仅能移动到(i+1,j)或(i,j+1)，结果需取10^9+7的模。

示例迷宫：

0 0 0 
0 -1 0 
0 0 0

对应两条路径，答案为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;
    }
}

二维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的二维ArrayList并累加DP数组，但该版本运行结果错误，二维数组版本却能正常通过测试。请帮我找出二维ArrayList版本中的错误。

问题出在ArrayList.set()方法的返回值特性上：

• 二维数组版本中，dp[i][j] = ...是先计算右侧的路径和，赋值给dp[i][j]后返回该计算结果，逻辑正确。
• 而ArrayList版本中，dp.get(i).set(j, ...)方法返回的是该位置修改前的旧值，而非你刚设置的新路径和。比如第一次给dp[i][j]赋值时，旧值是初始化的-1，所以set方法会返回-1，而非计算出的正确路径数，直接导致递归返回错误值，整个DP逻辑完全偏离预期。

修复方法 #

将返回语句拆分为两步：先计算路径和并设置到ArrayList中，再返回这个计算后的新值，同时注意每次加法后取模避免溢出：

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

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

修改后，ArrayList版本的逻辑与二维数组版本完全一致，即可得到正确结果。

内容的提问来源于stack exchange，提问作者Anonymous