给你一个 m * n的矩阵mat和一个整数K，请你返回一个矩阵 answer ，其中每个answer[i][j]是所有满足下述条件的元素mat[r][c]的和：
i - K <= r <= i + K, j - K <= c <= j + K(r, c) 在矩阵内。示例 1：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1 输出：[[12,21,16],[27,45,33],[24,39,28]]示例 2：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2 输出：[[45,45,45],[45,45,45],[45,45,45]]提示：
m == mat.lengthn == mat[i].length1 <= m, n, K <= 1001 <= mat[i][j] <= 100解题思路：
该题要求我们求出每一个区域矩阵的和,区域矩阵是以(i,j)为中心，长宽为(2K+1,2K+1)的矩阵，因为题目要求我们求出以每一个点为中心的矩阵的值，因此我们研究一下可以发现，如果以点来向右移动，则两个相邻的矩阵只有一条边的数值发生了变化（我们把矩阵看成由2K+1个列组成的），该边就是矩阵的最左边的一条边，因此我们可以用dp[i][j]来表示点(i,j)所在的边的值
如：
1 2 3 4 5 6 7 8 9 K = 1则点(0,0)的矩阵就是
1 2 4 5此时dp[0][0] = 1 + 4 , 按理说它应该加它上面一个值的，但是超过mat数组的范围了，因为该矩阵的一部分mat数组外部
dp[0][1] = 2 + 5
所以以(0,0)为中心的矩阵的大小就是 dp[0][0] + dp[0][1]
因此我们现在的问题就是求出dp数组了
因为dp[i][j]的含义是点(i,j)所在边的长度,求的方法就是往上遍历K个数字，再往下遍历K个数字，最后加上自身就是当前边的值
如：
1 2 3 4 5我们假设K=2,此时
第一条边就是[null,null,1,2,3]第二条边就是[null,1,2,3,4]第三条边就是[1,2,3,4,5]第四条边就是[2,3,4,5,null]第五条边就是[3,4,5,null,null]因此dp数组的转移方程就是
dp[i][j] = dp[i-1][j]; //首先等于前面一条边的值 if(i-1-K>=0) //减去前面一条边的头部如果存在 dp[i][j] -= mat[i-1-K][j]; if(i+K<dp.length) //加上新的尾部如果存在 dp[i][j] += mat[i+K][j];代码如下：
class Solution { public int[][] matrixBlockSum(int[][] mat, int K) { int[][] dp = new int[mat.length][mat[0].length]; int[][] answer = new int[mat.length][mat[0].length]; for(int j=0; j<dp[0].length; j++) //初始化第一行的每一条边 { for(int i=0; i<=K; i++) dp[0][j]+=mat[i][j]; } for(int i=1; i<dp.length; i++) //求dp数组 { for(int j=0; j<dp[0].length; j++) { dp[i][j] = dp[i-1][j]; if(i-1-K>=0) dp[i][j] -= mat[i-1-K][j]; if(i+K<dp.length) dp[i][j] += mat[i+K][j]; } } for(int i=0; i<dp.length; i++) //求出最左边的每一个矩阵的值，因为后面我们要向右移动，向右移动的过程就是减去最左边的边加上新的最右边的边 //我们不向下移动，因此要求出每一行的第一个矩阵的值 { for(int j=0; j<=K&&j<dp[0].length; j++) answer[i][0] += dp[i][j]; } for(int i=0; i<answer.length; i++) //遍历每一行的第一个矩阵 { for(int j=1; j<answer[0].length; j++)//遍历当前行的所有点 { answer[i][j] = answer[i][j-1];//首先赋值 if(j-1-K>=0) //类似dp数组，如果最左边的边存在就减去 answer[i][j] -= dp[i][j-1-K]; if(j+K<answer[0].length) //如果最右边的边存在就加上 { answer[i][j] += dp[i][j+K]; } } } return answer; } }时间复杂度O(mat.length*mat[0].length)
空间复杂度O(mat.length*mat[0].length)
