304. 二维区域和检索 - 矩阵不可变—

304. 二维区域和检索 - 矩阵不可变——动态规划

本文主要是介绍304. 二维区域和检索 - 矩阵不可变——动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一维前缀和

class NumMatrix {
public:vector<vector<int>> dp;NumMatrix(vector<vector<int>>& matrix) {//一开始思考，不是每次直接加起来就好了吗//后来发现，这样消耗的时间也太多了吧，怪不得我AC不了//看了题解才知道，看起来越简单的题，越要用精妙的方法去做int rows = matrix.size(), cols = matrix[0].size();dp.resize(rows, vector<int>(cols + 1));//按行计算所处单元格的行前缀和for(auto row = 0; row < rows; ++row){for(auto col = 0; col < cols; ++col){dp[row][col + 1] = dp[row][col] + matrix[row][col];}}}int sumRegion(int row1, int col1, int row2, int col2) {int sum = 0;//每行的和就是每行col2 + 1的前缀和减去col1的前缀和for(auto i = row1; i <= row2; ++i){sum += dp[i][col2 + 1] - dp[i][col1];}return sum;}
};

Accepted
24/24 cases passed (512 ms)
Your runtime beats 8.77 % of cpp submissions
Your memory usage beats 64.22 % of cpp submissions (144.5 MB)

二维前缀和

在这里插入图片描述
如图，范围内的和为dp[i + 1][j+ 1] - dp[i + 1][j] - dp[i][j + 1] + dp[i][j]
那么重要的是dp[i][j]的普遍公式是如何得到的？
仔细思考后发现，和上面的有异曲同工之妙
dp[row + 1][col + 1] = dp[row + 1][col] + dp[row][col + 1] - dp[row][col] + matrix[row][col];

class NumMatrix {
public:vector<vector<int>> dp;NumMatrix(vector<vector<int>>& matrix) {int rows = matrix.size(), cols = matrix[0].size();dp.resize(rows + 1, vector<int>(cols + 1));for(auto row = 0; row < rows; ++row){for(auto col = 0; col < cols; ++col){dp[row + 1][col + 1] = dp[row + 1][col] + dp[row][col + 1] - dp[row][col] + matrix[row][col];}}}int sumRegion(int row1, int col1, int row2, int col2) {return dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1];}
};