An easy C++ DP solution with simple explanation


  • 0

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

Log in to reply
 

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