# 7 lines C++ DP with explanation

• Let me explain the idea with a graph showing below:

Main idea : Sum(Red) = Sum(Blue) - Sum(Green) - Sum(Orange) + Sum(Black)

And we just need to know the sum from (0, 0) to any grid(i, j):

Steps:

• First, we store the sum from (0, 0) to any grid(i, j) in the matrix in a 2D vector - denoted as `dp`;

• For the first row of the matrix, `dp[0][j]` = it's value + `dp[0][j - 1]`;

• For the first column of the matrix, `dp[i][0]` = it's value + `dp[i - 1][0]`;

• For other grid in matrix, `dp[i][j]` = it's val + `dp[i][j - 1]` + `dp[i - 1][j]` - `dp[i - 1][j - 1]`;

• Now we have the value of (0, 0) to any grid(i, j).

Code:

``````class NumMatrix {
public:
NumMatrix(vector<vector<int>> matrix) {
for(int i = 0; i < matrix.size(); i++){
dp.push_back(vector<int>());
for(int j = 0; j < matrix[0].size(); j++)
if(i == 0)
if(j == 0) dp[i].push_back(matrix[0][0]);
else dp[i].push_back(matrix[0][j] + dp[0][j - 1]);
else
if(j == 0) dp[i].push_back(matrix[i][j] + dp[i - 1][0]);
else dp[i].push_back(matrix[i][j] + dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]);
}
}

int sumRegion(int row1, int col1, int row2, int col2) {
int a = (row1 == 0) ? 0 : dp[row1 - 1][col2];
int b = (col1 == 0) ? 0 : dp[row2][col1 - 1];
int c = (row1 == 0 || col1 == 0) ? 0 : dp[row1 - 1][col1 - 1];
return dp[row2][col2] - a - b + c;
}

private:
vector<vector<int>>dp;
};
``````

Or a more concise one, 7 lines.

``````class NumMatrix {
public:
NumMatrix(vector<vector<int>> matrix) {
for(int i = 0; i < matrix.size(); i++){
dp.push_back(vector<int>());
for(int j = 0; j < matrix[0].size(); j++)
if(i == 0) dp[i].push_back(!j ? matrix[0][0] : matrix[0][j] + dp[0][j - 1]);
else dp[i].push_back(!j ? matrix[i][j] + dp[i - 1][0] : matrix[i][j] + dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]);
}
}

int sumRegion(int row1, int col1, int row2, int col2) {
return dp[row2][col2] - (!row1 ? 0 : dp[row1 - 1][col2]) - (!col1 ? 0 : dp[row2][col1 - 1]) + (!row1 || !col1 ? 0 : dp[row1 - 1][col1 - 1]);
}

private:
vector<vector<int>>dp;
};
``````

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