前缀和数组技巧 [labuladong-刷题打卡 day3]

今天是两道前缀和，主要有一维前缀和和二维前缀和，当然扩充到高维也是可以的，只不过状态转移会相对复杂些。
这里直接贴一个动态规划的介绍吧：
动态规划要素
动态规划概念、特点、经典例题和于其它算法思想的比较
前缀和其实是备忘录自底向上动态规划算法的一个典型例子，状态转移方程：
一维：sums[i]=sums[i-1]+nums[i]
二维： sums(i,j)=sums(i−1,j)+sums(i,j−1)−sums(i−1,j−1)+matrix[i][j]

这里直接贴一个二维题解：
304. 二维区域和检索 - 矩阵不可变

class NumMatrix {
private:
    vector<vector<int>> preSum;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int row=matrix.size();
        if(row==0) return;
        int col=matrix[0].size();
        preSum.resize(++row,vector<int>(++col));
        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]-preSum[i-1][j-1]+matrix[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2+1][col2+1]-preSum[row1][col2+1]-preSum[row2+1][col1]+preSum[row1][col1];
    }
};