05 August 2008
与1314矩阵区域和类似，也是使用前缀和来计算矩阵和
设dp(x,y)为matrix数组的x行y列时的前缀和
为了方便计算dp数组比matrix数组行列各多1(dp数组第一行,第一列都为0)
前缀和公式 = 上面前缀和+左边前缀和-左上前缀和
dp(x+1,y+1) = dp(x,y+1)+ dp(x+1,y)- dp(x,y)+ matrix(x,y)
r1,c1表示matrix数组左上角坐标;r2,c2表示matrix数组右上角坐标
矩阵和公式=右下前缀和-左下的左边前缀和-右上的上边前缀和+左上的左上角前缀和
因为dp数组比matrix数组多一行一列,所以使用前缀和时注意要+1
矩阵和=dp(r2+1,c2+1) - dp(r2+1,c1) - dp(r1,c2+1) + dp(r1,c1)
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
44
45
46
47
48
49
50
51
52
53
54
class NumMatrix {
/*
http://blog.csdn.net/zdavb/article/details/49807841
每个点的值为以(0,0)为左上角，以该点为右下角的全部和。
当计算（row1，col1)到（row2,col2)时，就是计算newMatrix[row2][col2] - newMatrix[row2-1][col1] - newMatrix[row1][col2-1] + newMatrix[row1-1][col1-1].
为了代码方便，不放添加一个空的行和一列，这样就不用判断是否越界了。
*/
int[][] sumMatrix;
int row;
int col;
boolean noVal = false;
public NumMatrix(int[][] matrix) {
this.row = matrix.length;
if (row == 0) {
noVal = true;
return;
}
this.col = matrix[0].length;
if (col == 0) {
noVal = true;
return;
}
sumMatrix = new int[row + 1][col + 1];
// for (int i = 0; i < row + 1; i++) {
// sumMatrix[i][0] = 0;
// }
// for (int i = 0; i < col + 1; i++) {
// sumMatrix[0][i] = 0;
// }
// init other
for (int i = 1; i < row + 1; i++) {
for (int j = 1; j < col + 1; j++) {
sumMatrix[i][j] = sumMatrix[i-1][j] + sumMatrix[i][j-1] - sumMatrix[i-1][j-1] + matrix[i-1][j-1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
if (noVal) {
return 0;
}
return sumMatrix[row2 + 1][col2 + 1] - sumMatrix[row2 + 1][col1] - sumMatrix[row1][col2 + 1] + sumMatrix[row1][col1];
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/
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
class NumMatrix {
private int[][] dp;
public NumMatrix(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
dp = new int[rows + 1][cols + 1];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + matrix[i][j];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1];
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/