Range Sum Query 2D - Immutable
給定一個二維數(shù)組，求一個方塊內(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];
    }
};