LeetCode 1314
矩阵区域和
给你一个 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.length
- n == mat[i].length
- 1 <= m, n, K <= 100
- 1 <= 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 9K = 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)