# An easy C++ DP solution with simple explanation

• `v[i][j]` used to save the sum of rectangle (0, 0, i, j) which means rectangle's upper left corner is (0, 0), lower right corner is (i, j).

・v[i][j]=`matrix[i][j]+matrix[i-1][j]+matrix[i][j-1]-matrix[i-1][j-1];` //i and j should > 0

・region area = `v[i][j]+v[row1 - 1][col1 - 1]-v[row1 - 1][col2]-v[row2][col1 - 1];` //i and j should > 0

``````class NumMatrix
{
vector<vector<int>> v;
public:
NumMatrix(vector<vector<int>> &mat)
{
if (!mat.size() || !mat[0].size())
return;
int nrow = mat.size();
int ncol = mat[0].size();
v = mat;
int i, j;
for (i = 0; i < nrow; ++i)
{
for (j = 0; j < ncol; ++j)
{
if (i>0 && j>0)
v[i][j] = v[i][j] - v[i - 1][j - 1];
if (i > 0)
v[i][j] += v[i - 1][j];
if (j > 0)
v[i][j] += v[i][j - 1];
}
}
}

int sumRegion(int row1, int col1, int row2, int col2)
{
int ret = v[row2][col2];
if (row1 > 0 && col1 > 0)
ret += v[row1 - 1][col1 - 1];
if (row1 > 0)
ret = ret - v[row1 - 1][col2];
if (col1 > 0)
ret = ret - v[row2][col1 - 1];
return ret;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.