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

题目描述

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。

示例:

给定 matrix = [

[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ]

sumRegion(2, 1, 4, 3) -> 8

sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/range-sum-query-2d-immutable 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

C++

暴力超时非得动态规划

class NumMatrix {
   public:    vector
   
    
     > sums;         //动态规划     //表中递归关系式f（i,j）为以i,j为右下角元素的矩阵的元素和     //f(i,j)=f(i,j-1)+f(i-1,j)-f(i-1,j-1)+matrix[i][j]    NumMatrix(vector
     
      
       >& matrix) {
           int m = matrix.size();        if (m > 0) {
               int n = matrix[0].size();            sums.resize(m + 1, vector
       
        (n + 1));            for (int i = 0; i < m; i++) {
                   for (int j = 0; j < n; j++) {
                       sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];                }            }        }    }    int sumRegion(int row1, int col1, int row2, int col2) {
           return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];    }};