LeetCode661-图片平滑器
传送门 二维前缀和，定义f[i][j]为从矩阵左上角(0,0)到当前位置(i-1,j-1)的元素之和，那么任意一个3x3小矩阵内的9个元素之和就是tot=f[i+2][j+2] - f[i+2][j-1] - f[i-1][j+2] + f[i-1][j-1] 提一下这个状态转移方程需要注意的几个点：因为多减了一次f[i-1][j-1]，所以要加回来；f[i][j]做了下标偏移是因为需要用到f[i+2][j-1]和f[i-1][j+2]来计算区域和。 class Solution { public: vector<vector<int>> imageSmoother(vector<vector<int>>& img) { int m = img.size(); int n = img[0].size(); vector<vector<int>> f(m+1, vector<int>(n+1)); vector<vector<int>> ans(m, vector<int>(n)); // 二维前缀和 // f[i][j]表示从(0,0)到(i-1,j-1)的区域内元素之和 // 比起传统的二维前缀和，做了下标偏移 // 因为后面计算时需要用到f[lx][ry+1]和f[rx+1][ly]计算区域和 for (int i = 1; i <= m; …