【动态规划】leetcode-1314.

  • 时间:
  • 浏览:
  • 来源:互联网

题目:

给你一个 m * n 的矩阵 mat 和一个整数 K ,请你返回一个矩阵 answer ,其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和:

  1. i - K <= r <= i + K, j - K <= c <= j + K
  2. (r, c) 在矩阵内。
    在这里插入图片描述

解答:

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        m=len(mat)
        n=len(mat[0])
        dp=[[0]*(n+1) for _ in range(m+1)]

        #先求出前缀和
        for i in range(1,m+1):
            for j in range(1,n+1):
                dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+mat[i-1][j-1]
                
        #计算answer矩阵
        answer=[[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                ru=max(0,i-K)
                rd=min(i+K,m-1)
                cl=max(0,j-K)
                cr=min(j+K,n-1)
                print(ru,cl,rd,cr)
                answer[i][j]=dp[rd+1][cr+1]-dp[rd+1][cl]-dp[ru][cr+1]+dp[ru][cl]
        return answer

本文链接http://www.dzjqx.cn/news/show-617537.html