Range Sum Query 2D - Immutable
給定一個(gè)二維數(shù)組，求一個(gè)方塊內(nèi)所有元素之和((row1, col1) 與 (row2, col2))，這道題跟leetcode303是很像的，這里只是一維數(shù)組變二維數(shù)組坛掠。這里是記錄從(0, 0) 到 (r, c)的和
建議先去看一下leetcode303
Leetcode 303. Range Sum Query - Immutable, Terence_F的文章
class NumMatrix {
int row, column;
vector<vector<int>> dp;
public:
NumMatrix(vector<vector<int>> &matrix) {
row = matrix.empty() ? 0 : matrix.size();
column = row ? matrix[0].size() : 0;
dp = vector<vector<int>>(row + 1, vector<int>(column + 1, 0));
for (int r = 1; r <= row; r++) {
for (int c = 1; c <= column; c++) {
dp[r][c] = dp[r - 1][c] + dp[r][c - 1] - dp[r - 1][c - 1] + matrix[r - 1][c - 1];
}
}
}
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];
}
};
