1: class NumMatrix { 2: private: 3: vector<vector<int>> dp; 4: vector<vector<int>> table; 5: int rows; 6: int cols; 7: public: 8: NumMatrix(vector<vector<int>> &matrix) { 9: table = matrix; 10: rows = matrix.size(); 11: if (rows == 0) return; 12: cols = matrix[0].size(); 13: dp = vector<vector<int>>(rows, vector<int>(cols, 0)); 14: for (int i = 0; i < rows; i++) { 15: for (int j = 0; j < cols; j++) { 16:
dp[i][j] = (j == 0) ? matrix[i][j] : dp[i][j-1] + matrix[i][j];
17: } 18: for (int j = 0; j < cols; j++) { 19: dp[i][j] += (i == 0) ? 0 : dp[i-1][j]; 20: } 21: } 22: } 23: void update(int row, int col, int val) { 24: int diff = val - table[row][col]; 25: table[row][col] = val; 26: for (int i = row; i < rows; i++) { 27: for (int j = col; j < cols; j++) { 28: dp[i][j] += diff; 29: } 30: } 31: } 32: int sumRegion(int row1, int col1, int row2, int col2) { 33: if (row1 == 0 && col1 == 0) return dp[row2][col2]; 34: if (row1 == 0) return dp[row2][col2]-dp[row2][col1-1]; 35: if (col1 == 0) return dp[row2][col2]-dp[row1-1][col2]; 36: return dp[row2][col2]-dp[row1-1][col2]-dp[row2][col1-1]+dp[row1-1][col1-1]; 37: } 38: }; 39: // Your NumMatrix object will be instantiated and called as such: 40: // NumMatrix numMatrix(matrix); 41: // numMatrix.sumRegion(0, 1, 2, 3); 42: // numMatrix.update(1, 1, 10); 43: // numMatrix.sumRegion(1, 2, 3, 4);
Thursday, July 14, 2016
308. Range Sum Query 2D - Mutable
I followed the same way to solve problem “303. Range Sum Query - Immutable”, i.e. dp[i][j] is the sum of rectangle (0, 0, i, j). So the area of rectangle (i1, j1, i2, j2) will be dp[i2][j2]-dp[i1-1][j2]-dp[i2][j1-1]+dp[i1-1][j1-1]. When I revisited this problem, I made mistake in line 16 in red.
Labels:
dynamic programming,
leetcode,
math,
matrix
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment