leetcode：1314. 矩阵区域和【二维前缀和模板】

分析

二维前缀和模板
dp的时候多一行一列记录0方便统一式子

ac code

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        # 二维前缀和
        m, n = len(mat), len(mat[0])
        # row and col 补充一行全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

总结

二维前缀和板子