C ++中矩阵（或2D数组）的前缀和
在这个问题中，我们得到了一个二维整数数组mat[][]。我们的任务是打印mat的前缀和矩阵。
前缀求和矩阵：矩阵的每个元素都是其上下的和元素。即
prefixSum[i][j] = mat[i][j] + mat[i-1][j]...mat[0][j] + mat[i][j-1] +... mat[i][0].
让我们以一个例子来了解问题
Input: arr =[ [4 6 1] [5 7 2] [3 8 9] ] Output:[ [4 10 11] [9 22 25] [12 33 45] ]
为了解决这个问题，一个简单的解决方案是遍历所有元素直到i，j位置并添加它们，从而找到prefixSum。但这对于系统来说有点复杂。
一个更有效的解决方案是使用公式来查找prefixSum矩阵的元素的值。
ij位置元素的一般公式为
prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + a[i][j]
一些特殊情况
For i = j = 0, prefixSum[i][j] = a[i][j] For i = 0 and j > 0, prefixSum[i][j] = prefixSum[i][j-1] + a[i][j] For i > 0 and j = 0, prefixSum[i][j] = prefixSum[i-1][j] + a[i][j]
该代码显示了我们解决方案的实施
示例
#include <iostream>
using namespace std;
#define R 3
#define C 3
void printPrefixSum(int a[][C]) {
int prefixSum[R][C];
prefixSum[0][0] = a[0][0];
for (int i = 1; i < C; i++)
prefixSum[0][i] = prefixSum[0][i - 1] + a[0][i];
for (int i = 0; i < R; i++)
prefixSum[i][0] = prefixSum[i - 1][0] + a[i][0];
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++)
prefixSum[i][j]=prefixSum[i- 1][j]+prefixSum[i][j- 1]-prefixSum[i- 1][j- 1]+a[i][j];
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++)
cout<<prefixSum[i][j]<<"\t";
cout<<endl;
}
}
int main() {
int mat[R][C] = {
{ 1, 2, 3},
{ 4, 5, 6},
{ 7, 8, 9}
};
cout<<"The prefix Sum Matrix is :\n";
printPrefixSum(mat);
return 0;
}输出结果
The prefix Sum Matrix is : 1 3 6 5 12 21 12 27 45