矩阵和 自上而下动态编程

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

你实际上是把许多单元格数了两次。

你应该这样写（我只是把一个+改为-）。

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

试着把矩阵画在纸上 然后写下你要加到你的总和上的单元格数 dp[i][j] 在计算小的i,j样本时(你在计算从(1,1)开始到(i-1,j-1)结束三次的矩形中的单元格)。

改变后，您可以从第一行开始，从左到右计算每一行的DP阵列。