number of submatrices

🏠

Not my solution. Need to investigate this more.

 1 class 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 
22 M = [[1,1,0],[1,1,1]]
23 
24 print(Solution().numSubmat(M))