使用 Python 计算所有子矩阵的程序

假设我们有 mxn 二进制矩阵，我们必须找出有多少个子矩阵都是 1。

所以，如果输入是这样的

那么输出将是 13，因为有 6 个 (1x1) 矩阵、3 个 (2,1) 矩阵、2 个 (1x2) 矩阵、1 个 (3x1) 矩阵和 1 个 (4x4) 矩阵。

为了解决这个问题，我们将按照以下步骤操作 -

• m := 矩阵的行数

• n := 矩阵的列数

• dp := 相同大小的零矩阵 mxn

• 对于 0 到 m - 1 范围内的 i，请执行

• 如果 i 与 0 和矩阵 [i, j] 相同，则

• 否则当 matrix[i][j] 非零时，则

• dp[i, j] := 1

• dp[i, j] := dp[i-1, j] + 1

• 对于 0 到 n - 1 范围内的 j，执行

• 总计：= 0

• 对于 0 到 m - 1 范围内的 i，请执行

• 对于 j+1 到 n 范围内的 k，做

• 总计 := 总计 + dp[i,j] 到 dp[i,k] 的最小值

• 对于 0 到 n - 1 范围内的 j，执行

• 总回报

让我们看看以下实现以获得更好的理解 -

示例

def solve(matrix):
   m = len(matrix)
   n = len(matrix[0])
   dp = [[0] * n for _ in range(m)]
   for i in range(m):
      for j in range(n):
         if i == 0 and matrix[i][j]:
            dp[i][j] = 1
         elif matrix[i][j]:
            dp[i][j] = dp[i-1][j] + 1
   total = 0
   for i in range(m):
      for j in range(n):
         for k in range(j+1, n+1):
            total += min(dp[i][j:k])
   return total
matrix = [[1,0,1],[0,1,1],[0,1,1]]
print(solve(matrix))

输入

[4,6,7,8], 11

13