矩阵求和自上而下的动态规划

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

尝试在一张纸上绘制矩阵，并尝试写下要添加到总和中的单元格，以便在计算小 i，j 样本时dp[i][j](您正在计算矩形中的单元格，该矩形从 (1,1( 开始，以 (i-1，j-1( 结束三次(。

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