Chương trình đếm các ma trận con với tất cả các ma trận con bằng Python

Giả sử chúng ta có m x n ma trận nhị phân, chúng ta phải tìm bao nhiêu ma trận con có tất cả các ma trận đó.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 13 vì có 6 (1x1) ma trận, 3 (2,1) ma trận, 2 (1x2) ma trận, 1 (3x1) ma trận và 1 (4x4) ma trận.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=số hàng của ma trận

• n:=số cột của ma trận

• dp:=ma trận không có cùng kích thước m x ​​n

• đối với tôi trong phạm vi từ 0 đến m - 1, hãy thực hiện

  • đối với j trong phạm vi 0 đến n - 1, thực hiện

    • nếu tôi giống 0 và ma trận [i, j] thì

      • dp [i, j]:=1

    • ngược lại khi ma trận [i] [j] khác 0 thì

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

• tổng:=0

• đối với tôi trong phạm vi từ 0 đến m - 1, hãy thực hiện

  • đối với j trong phạm vi 0 đến n - 1, thực hiện

    • đối với k trong phạm vi j + 1 đến n, thực hiện

      • tổng:=tổng + tối thiểu từ dp [i, j] đến dp [i, k]

• tổng trả lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

[4,6,7,8], 11

Đầu ra

13