本题题意
给出一个矩阵，再给定两个坐标，分别表示子矩阵左上角与右下角的坐标，求子矩阵元素总和。
例如：
矩阵 A=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]],子矩阵左上角坐标（0，1），右下角坐标（2，3）
那么，sum(0,1,2,3) = 2+3+4+6+7+8+10+11+12=63
思路：最直接的方法就是直接遍历子矩阵的所有元素，就可以搞定！时间复杂度为O(n^2)，但是超时了，因此需要优化。
受到积分图的启发，可以实现时间复杂度为O(1)!，什么！这么快。什么是积分图？
积分图的定义：矩阵中的某元素A的积分是矩阵左上角的顶点与A点围成的矩阵所有元素的总和。
即dp[i][j] = m(0,0)+m(0,1)+m(0,2)…+m(i,j);
因此，第一步先计算矩阵M中所有元素的积分dp[i][j]；
dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+m[i][j]; (i>=1,j>=1)
dp[i][j] = dp[i][j-1] + m[i][j]; (i==0)
dp[i][j] = dp[i-1][j] + m[i][j]; (j==0)
dp[i][j] = m[i][j]; (i==j==0)
计算完积分图后，求子矩阵元素和，就可以直接在O(1)的时间复杂度下计算出了。
子矩阵的两个坐标为a(row1,col1),b(row2,col2)
res = dp[row2][col2] - dp[row2][col1-1] - dp[row1-1][col2] + dp[row1-1][col1-1]; (row1>=1,col1>=1)
res = dp[row2][col2]-dp[row1-1][col2]; (col1==0) //第一列
res = dp[row2][col2] - dp[row2][col1-1]; (row1==0) //第一行
res = dp[row2][col2]; (row1==col1==0)
注意点：考虑边缘条件，矩阵m为空。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44class NumMatrix {
private:
bool empty;
vector<vector<int>> dp;
public:
NumMatrix(vector<vector<int>> &matrix) {
int row = matrix.size();
if(row >0)
{
empty = false;
int col = matrix[0].size();
dp.resize(row);
for (int i=0; i<row; ++i)
dp[i].resize(col);
dp[0][0]=matrix[0][0]; //处理原点
for(int j=1; j<col; ++j) //处理第一行
dp[0][j] = dp[0][j-1] + matrix[0][j];
for(int i=1; i<row; ++i) //处理第一列
dp[i][0] = dp[i-1][0] + matrix[i][0];
for (int i=1; i<row; ++i)
{
for (int j=1; j<col; ++j)
{
dp[i][j] = dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+matrix[i][j];
}
}
}
else
empty = true; //矩阵为空
}
int sumRegion(int row1, int col1, int row2, int col2) {
if(empty)
return 0;
if(row1==0 && col1==0)
return dp[row2][col2];
else if(row1==0)
return dp[row2][col2] - dp[row2][col1-1];
else if(col1==0)
return dp[row2][col2]-dp[row1-1][col2];
else
return dp[row2][col2] + dp[row1-1][col1-1] - dp[row2][col1-1] - dp[row1-1][col2];
}
};