圖片.png
- 基本思路：使用DP維護掂之，算法基本是小學(xué)奧數(shù)級別岭埠。
圖片.png
C++
class NumMatrix {
public:
NumMatrix(vector<vector<int> > &matrix) {
if (matrix.empty() || matrix[0].empty())
return;
dp.resize(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
for (int i = 1; i <= matrix.size(); ++i) {
for (int j = 1; j <= matrix[0].size(); ++j) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
}
private:
vector<vector<int> > dp;
};
Java
//faster
class NumMatrix {
private int[][] dp;
public NumMatrix(int[][] matrix) {
//this chunk is faster
if (null == matrix || 0 == matrix.length) {
return;
}
int m = matrix.length;
int n = matrix[0].length;
dp = new int[m + 1][n + 1];
//chunck end
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] =
matrix[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
}
}
}
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];
}
}
