7 lines C++ DP with explanation


  • 0

    Let me explain the idea with a graph showing below:

    0_1505974058300_lc.png

    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;
    };
    

Log in to reply
 

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