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

  • Z时代
  • 2024-01-10
  • 分类：综合

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

所以，如果输入是这样的

101
011
011

那么输出将是 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

      以上是 使用 Python 计算所有子矩阵的程序 的全部内容， 来源链接： utcz.com/z/361829.html

      回到顶部