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))