Range Sum Query 2D - Immutable
给定一个二维数组，求一个方块内所有元素之和((row1, col1) 与 (row2, col2))，这道题跟leetcode303是很像的，这里只是一维数组变二维数组。这里是记录从(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];
}
};
