矩阵和自顶向下动态规划

Question

给定一个矩阵。您需要打印矩形中左上角和右下角的所有数字的总和。

我使用自顶向下的动态规划方法来解决这个问题。查看我的代码。

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

输入

3 3
1 2 3
4 5 6
7 8 9
2
3 3
2 3

输出

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

预期产出

45
21

但当输入查询时，这会抛出非常随机的数字。我没有得到我在这里缺少的东西。有人能帮忙吗？

谢谢✌️

Answer 1

在你计算的那条线上

dp[i][j]=findsum（arr，i-1，j）findsum（arr，i，j-1）findsum（arr，i-1，j-1）arr[i][j]

实际上，您正在对许多单元格进行两次计数。

你应该这样写这句话（我刚把a改成-）：

dp[i][j]=findsum（arr，i-1，j）findsum（arr，i，j-1）-findsum（arr，i-1，j-1）arr[i][j]

试着在一张纸上画出矩阵，并试着写下在计算小i，j样本时要添加到dp[i][j]和中的单元格（在矩形中计算单元格，从（1,1）开始，到（i-1，j-1）结束三次）。

更改后，可以从第一行开始，从左到右计算每行的DP数组。