问题：
给定一个二维数组，
求给定区间围成矩形的和。
Example 1: Input ["NumMatrix", "sumRegion", "sumRegion", "sumRegion"] [[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]] Output [null, 8, 11, 12] Explanation NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]); numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangele). numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangele). numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangele). Constraints: m == matrix.length n == matrix[i].length 1 <= m, n <= 200 -10^5 <= matrix[i][j] <= 10^5 0 <= row1 <= row2 < m 0 <= col1 <= col2 < n At most 10^4 calls will be made to sumRegion.
example 1:
解法：DP，preSum
1. 状态：dp[i][j]：[0,0]~[i-1,j-1]的矩形和
- i：i坐标
- j：j坐标
2.选择：
- dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
3.base:
- dp[0][j]=0
- dp[i][0]=0
而题目所求矩形[i1,j1]~[i2,j2]的和为：
- res=dp[i2][j2]-dp[i2][j1]-dp[i1][j2]+dp[i1][j1]
代码参考：
1 class NumMatrix { 2 public: 3 vector<vector<int>> dp; 4 NumMatrix(vector<vector<int>>& matrix) { 5 int n = matrix.size(); 6 int m = matrix[0].size(); 7 dp.resize(n+1, vector<int>(m+1, 0)); 8 for(int i=1; i<=n; i++) { 9 for(int j=1; j<=m; j++) { 10 dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+matrix[i-1][j-1]; 11 } 12 } 13 return; 14 } 15 16 int sumRegion(int row1, int col1, int row2, int col2) { 17 return dp[row2+1][col2+1]-dp[row2+1][col1]-dp[row1][col2+1]+dp[row1][col1]; 18 } 19 }; 20 21 /** 22 * Your NumMatrix object will be instantiated and called as such: 23 * NumMatrix* obj = new NumMatrix(matrix); 24 * int param_1 = obj->sumRegion(row1,col1,row2,col2); 25 */