I was trying to solve "Grid unique path" using Dynamic programming in Java

Question

I am trying to implement a solution for grid unique path using D.P. approach while trying to do so, I don't know why in the middle of execution the value at (0,1) location gets negative while I'm giving the addition sign the answer getting stored is (-2). Whereas the recursion is giving absolute perfect answer at DP(0,2) PLUS DP(1,1), as you can see in the matrix they're positive values. I tried several output lines to debug and find the problem but was unable.

You'll need to focus on countPaths as that will be the function that modifies array

CODE:

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

OUTPUT:

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

So the line causing the erroneous output was return dp.get(i).set(j,(countPaths(i,j+1,m,n,dp)+countPaths(i+1,j,m,n,dp)));

this line is erroneous because I was returning the element that is to be setted and thus a value of previous copy of array was executed and sent out. (That's my guess).

Thus I made a change that'll first calculate the recursive value and then store it.

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

now the output are desirable