Matrix Sum Top down Dynamic Programming

Question

Problem

You are given a matrix. You need to print the sum of all the numbers in the rectangle which has as the top left corner and as the bottom right corner.

I'm using top down dynamic programming approach to solve this problem. see my code.

import java.util.*;
public class Matrixsum
{

    static int dp[][] = new int[4][4]; // for debugging max size 1001,1001

    static int findsum(int arr[][] , int i, int j)
    {
        if(i<1 || j < 1) return 0;
        if(dp[i][j] != -1)
            return dp[i][j];
        else
dp[i][j] = findsum(arr,i-1,j)+findsum(arr,i,j-1)+findsum(arr,i-1,j-1)+arr[i][j];
        return dp[i][j];
    }

    public static void main(String[] args)
    {
            for(int[] d:dp) Arrays.fill(d,-1);
            Scanner sc = new Scanner(System.in);
            int a = sc.nextInt();
            int b = sc.nextInt();
            int arr[][] = new int[1001][1001];
            for(int i=0;i<a;i++)
            {
                for (int j = 0; j < b; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }

            int q = sc.nextInt();
            while(q-- > 0)
            {
                int i = sc.nextInt();
                int j = sc.nextInt();
                System.out.println(findsum(arr,i,j));
            }
            System.out.println(Arrays.deepToString(dp));
         //   dp = new int[1001][1001];
        }
}

Input

Output

162
60
[[-1, -1, -1, -1], [-1, 5, 11, 11], [-1, 13, 38, 60], [-1, 13, 64, 162]]

Expected output

45
21

But this is throwing very random numbers when query is entered . I'm not getting what's I'm missing here. Can somebody help ?

Thanks ✌️

I'm really confused. You're just supposed to sum all elements. How can you split it into recursive problem? If anything, you need to split the matrix into n submatrices that are disjoint. — Amongalen
I created 2 Matrix for each smaller mat but this gives me TLE so I had to use dynamic programming. — Aashish Pawar
Just iterate over all elements in the area and sum them. No need for 2 matrices. You're overcomplicating it. — Amongalen
Constraints of the problem is very large size of matrix upto 10^3 and no of queries can be upto 10^5 So if I calculate again and again for new Query then it will exceed the time limit. — Aashish Pawar
It is still unclear to me what you want to do here. In the question you said "You are given a matrix. You need to print the sum of all the numbers in the rectangle which has as the top left corner and as the bottom right corner." To be honest I don't even know i and j are supposed to be. Are you trying to say you want to create a lookup table with all possible combinations of queries? You don't have enough memory for that. — Amongalen

A.A A.A · Accepted Answer · 2020-06-08T11:02:57

In the line where you calculate

dp[i][j] = findsum(arr,i-1,j)+findsum(arr,i,j-1)+findsum(arr,i-1,j-1)+arr[i][j];

you are actually counting many cells twice.

You should write that line this way (I just changed a + to -):

dp[i][j] = findsum(arr,i-1,j)+findsum(arr,i,j-1)-findsum(arr,i-1,j-1)+arr[i][j];

Try drawing the matrix on a piece of paper and try to write down the cells you are adding to your sum for dp[i][j] in the calculation for small i,j samples (you are counting cells in the rectangle which starts at (1,1) and ends in (i-1,j-1) three times).

After changing this you can start from the first row and calculate your DP array from left to right for each row.

Matrix Sum Top down Dynamic Programming

Problem

1 Answers