本文共 2035 字，大约阅读时间需要 6 分钟。

1. 题目

2. 解题

类似题目：

dp[i][j]数组表示 从左上角到i,j位置的所有和

class NumMatrix {
   	vector
   
    
     > sum;public:    NumMatrix(vector
     
      
       >& matrix) {
           if(matrix.empty())            return;        int r = matrix.size(), c = matrix[0].size(), i, j;        sum = vector
       
        
         > (r+1, vector
         
          (c+1, 0)); for(i = 0; i < r; i++) { for(j = 0; j < c; j++) { sum[i+1][j+1] = sum[i+1][j]+sum[i][j+1]+matrix[i][j]-sum[i][j]; } } } int sumRegion(int row1, int col1, int row2, int col2) { if(sum.empty()) return 0; return sum[row2+1][col2+1] - sum[row1][col2+1] - sum[row2+1][col1] + sum[row1][col1]; }};
         
        
       
      
     
    
   

or

class NumMatrix {
   	vector
   
    
     > sumofrows;public:    NumMatrix(vector
     
      
       >& matrix) {
           if(matrix.empty())            return;        int r = matrix.size(), c = matrix[0].size(), i, j, sum = 0;        vector
       
         temp(c,0);        for(i = 0; i < r; i++)        {
           	sum = 0;        	for(j = 0; j < c; j++)        	{
           		sum += matrix[i][j];        		temp[j] = sum;        	}        	sumofrows.push_back(temp);        }    }        int sumRegion(int row1, int col1, int row2, int col2) {
           if(sumofrows.empty())            return 0;        int i, j, sum = 0;        if(col1 != 0)            for(i = row1; i <= row2; i++)            {
                   sum += sumofrows[i][col2]-sumofrows[i][col1-1];            }        else            for(i = row1; i <= row2; i++)            {
                   sum += sumofrows[i][col2];            }        return sum;    }};/** * Your NumMatrix object will be instantiated and called as such: * NumMatrix* obj = new NumMatrix(matrix); * int param_1 = obj->sumRegion(row1,col1,row2,col2); */
       
      
     
    
   

转载地址：https://michael.blog.csdn.net/article/details/101219854 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！