1314. 矩阵区域和

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

和

 

64. 最小路径和

一样的套路

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 i in range(m+1)]#设成(n+1),(m+1)防止后面的i-1，j-1越界
        for i in range(1,m+1):
            for j in range(1,n+1):
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1]
        def sum(x1,y1,x2,y2):
            x1=max(0,x1)
            y1=max(0,y1)
            x2=min(m-1,x2)
            y2=min(n-1,y2)
            return dp[x2+1][y2+1]+dp[x1][y1]-dp[x1][y2+1]-dp[x2+1][y1]#画图理解
        res=[[0]*n for i in range(m)]
        for i in range(m):
            for j in range(n):
                res[i][j]=sum(i-k,j-k,i+k,j+k)
        return res