Make writing a habit together! This is the fifth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

The title

Matrix region sum

Where each answer[I][j] is the sum of all elements mat[r][c] that satisfy the following conditions:

I-k <= r <= I + k, j-k <= c <= j + k and (r, c) is in the matrix.

Example 1:

Input: mat = [[1, 2, 3], [4 and 6], [7,8,9]], k = 1 output: [,21,16 [12], [27,45,33], [24,39,28]]Copy the code

Example 2:

Input: mat = [[1, 2, 3], [4 and 6], [7,8,9]], k = 2 output: [[45,45,45], [45,45,45], [45,45,45]]Copy the code

Tip:

m == mat.length
n == mat[i].length
1 <= m, n, k <= 100
1 <= mat[i][j] <= 100
Copy the code

Answer key

Analysis of the problem solving

Their thinking

  1. The problem is a typical dynamic programming problem;
  2. Get prefix matrix dp[][]
dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]+arr[i][j]-dp[i][j];
Copy the code
  1. According to the prefix matrix
  • The core problems are as follows: 1) to find the transfer equations of the two processes; 2). Boundary processing.
  1. The solution code is as follows:

Complexity Time complexity: O(M x N) Space complexity: O(M x N)

The problem solving code

The solution code is as follows (there are detailed notes in the code) :

class Solution {
    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);
    }
    // Get the dp array
    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;
    }
    // Get the result
    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]; }}returnres; }}Copy the code

Feedback results after submission (because the topic has not been optimized, the performance is mediocre) :

The reference information

  • Force buckle LeetCode 1314. Matrix area and
  • Dynamic programming