题目链接
题目描述
实现代码
前缀和的思想,首先记dp[i][j]表示从(0,0)位置到(i,j)位置组成的矩形区域和;状态转移方程为:
dp[i][j] = dp[i-1][j] + dp[i][j-1] + mat[i][j] - dp[i-1][j-1]
可由下图直观看出
然后,该题要求的结果记res[i][j],则将其画出来可以看到,res[i][j]可以通过dp[i][j]进行表示,如下图:
实现代码如下:
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length,n = mat[0].length;
int[][] dp = get_dp(mat,m,n);
return get_res(dp,m,n,k);
}
//获取dp数组
public int[][] get_dp(int[][] arr,int m,int n){
int[][] dp = new int[m+1][n+1];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]+arr[i][j]-dp[i][j];
return dp;
}
//获取结果
public int[][] get_res(int[][] dp,int m,int n,int k){
int[][] res = new int[m][n];
int x1,y1,x2,y2;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
x1 = Math.max(0,i-k);y1 = Math.max(0,j-k);
x2 = Math.min(m,i+k+1);y2 = Math.min(n,j+k+1);
res[i][j] = dp[x2][y2]-dp[x1][y2]-dp[x2][y1]+dp[x1][y1];
}
}
return res;
}