number of submatrices

🏠

Not my solution. Need to investigate this more.

 1class Solution:
 2    def numSubmat(self, mat):
 3        h, w = len(mat),len(mat[0])     
 4        dp = [[None for i in range(w)]for j in range(h)]
 5        for i in range(h):
 6            count=0
 7            for j in range(w-1,-1,-1):
 8                count = count + mat[i][j] if mat[i][j] else 0
 9                dp[i][j]=count
10        for r in dp:
11            print(r)
12        ans = 0
13        for i in range(h):
14            for j in range(w):
15                mn = float('inf')
16                for k in range(i, h):
17                    mn = min(mn, dp[k][j])
18                    ans += mn
19        return ans
20
21
22M = [[1,1,0],[1,1,1]]
23
24print(Solution().numSubmat(M))