我试图使用 Java 中的动态编程来解决"Grid unique path"

Question

我正在尝试使用dp实现网格唯一路径的解决方案方法在尝试这样做的同时，我不知道为什么在执行过程中，(0,1)位置的值变为负值，而我给出了加号，存储的答案是(-2)。而递归在DP(0,2)+DP(1,1)时给出了绝对完美的答案，正如你在矩阵中看到的，它们都是正值。我尝试了几个输出行来调试并找到问题，但无法找到。

您需要关注countPaths，因为这将是修改数组

的函数代码:

public static void main(String[] args) {
int totalCount = uniquepath(2,3);
System.out.println(totalCount);
}
public static int uniquepath(int m, int n) {
ArrayList<ArrayList<Integer>> dp =new ArrayList<ArrayList<Integer>>(m+1);
//ArrayList<Integer> mp = new ArrayList<Integer>(Collections.nCopies(n, -1));
for(int k = 0; k<m+1; k++) {                        
dp.add(k, new ArrayList<Integer>(Collections.nCopies(n+1, -1)));
}
int num = countPaths(0,0,m,n,dp);
System.out.println(dp.get(0));
System.out.println(dp.get(1));
System.out.println(dp.get(2));
return num;
}

public static int countPaths(int i, int j, int m, int n, ArrayList<ArrayList<Integer>> dp) {
//3 conditions 
//1. if you're at the end then return 1
//2. if you're beyond OR at the boundary then return 0
//3. if you're the matrix is having -1 value then store the computed value 
//3a. else you're to countpaths from right and the left path
System.out.println(i+" "+j);
System.out.println(dp.get(0));
System.out.println(dp.get(1));
System.out.println(dp.get(2));
System.out.println();
if(i==(m-1)&&j==(n-1)) return 1;
if(i>=m||j>=n) return 0;
if(dp.get(i).get(j) != -1) {System.out.println("upper part executed "); 
return dp.get(i).get(j);}
else return dp.get(i).set(j,(countPaths(i,j+1,m,n,dp)+countPaths(i+1,j,m,n,dp))); 
}

输出:

0 0
[-1, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]
0 1
[-1, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]
0 2
[-1, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]
0 3
[-1, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]
1 2
[-1, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]
1 1
[-1, -1, 1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]
1 2
[-1, -1, 1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]
2 1
[-1, -1, 1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]
1 0
[-1, **-2**, 1, -1]
[-1, 1, -1, -1]
[-1, -1, -1, -1]
1 1
[-1, -2, 1, -1]
[-1, 1, -1, -1]
[-1, -1, -1, -1]
hi 
2 0
[-1, -2, 1, -1]
[-1, 1, -1, -1]
[-1, -1, -1, -1]
[-2, -2, 1, -1]
[1, 1, -1, -1]
[-1, -1, -1, -1]
-1

Answer 1

所以导致错误输出的行是return dp.get(i).set(j,(countPaths(i,j+1,m,n,dp)+countPaths(i+1,j,m,n,dp)));

这一行是错误的，因为我正在返回要设置的元素，因此执行并发送了数组的前一个副本的值。(这是我的猜测)。

因此，我做了一个更改，首先计算递归值，然后存储它。

int s = countPaths(i,j+1,m,n,dp)+countPaths(i+1,j,m,n,dp);
dp.get(i).set(j,(s)); 
return s;
}

现在输出是理想的