leetcode：1314. Matrix area and [2D prefix and template]

analysis

2D prefix and template
dp One more row and one more column of records 0 Convenient unified formula

ac code

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        #  Two dimensional prefixes and 
        m, n = len(mat), len(mat[0])
        # row and col  Add a full line 0
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        dp[1][1] = mat[0][0]
        for j in range(2, n + 1):
            dp[1][j] = mat[0][j - 1] + dp[1][j - 1]
        for i in range(2, m + 1):
            dp[i][1] = mat[i - 1][0] + dp[i - 1][1]
        for i in range(2, m + 1):
            for j in range(2, n + 1):
                #print(i, j)
                dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
        #print(dp)
        res = [[0] * n for _ in range(m)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                left, right = max(i - k, 1), min(m, i + k)
                up, down = max(j - k, 1), min(n, j + k)
                res[i - 1][j - 1] = dp[right][down] + dp[left - 1][up - 1] - dp[left - 1][down] - dp[right][up - 1]
        return res

summary

2D prefix and board