โปรแกรมนับเมทริกซ์ย่อยทั้งหมดโดยใช้ Python

สมมติว่าเรามีเมทริกซ์ไบนารี m x n เราต้องค้นหาว่าเมทริกซ์ย่อยมีทั้งหมดกี่ตัว

ดังนั้นหากอินพุตเป็นแบบ

1	0	1
0	1	1
0	1	1

จากนั้นผลลัพธ์จะเป็น 13 เนื่องจากมีเมทริกซ์ 6 (1x1) เมทริกซ์ 3 (2,1) เมทริกซ์ 2 (1x2) เมทริกซ์ 1 (3x1) เมทริกซ์ 1 (4x4) เมทริกซ์

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

m :=จำนวนแถวของเมทริกซ์
n :=จำนวนคอลัมน์ของเมทริกซ์
dp :=เมทริกซ์ศูนย์ที่มีขนาดเท่ากัน m x n
สำหรับฉันในช่วง 0 ถึง m - 1 ทำ
- สำหรับ j ในช่วง 0 ถึง n - 1 ทำ
  - ถ้าฉันเหมือนกับ 0 และเมทริกซ์[i, j] แล้ว
    - dp[i, j] :=1
  - มิฉะนั้นเมื่อ matrix[i][j] ไม่ใช่ศูนย์ ดังนั้น
    - dp[i, j] :=dp[i-1, j] + 1
รวม :=0
สำหรับฉันในช่วง 0 ถึง m - 1 ทำ
- สำหรับ j ในช่วง 0 ถึง n - 1 ทำ
  - สำหรับ k ในช่วง j+1 ถึง n ทำ
    - รวม :=รวม + ต่ำสุดของ dp[i,j] ถึง dp[i,k]
ผลตอบแทนรวม

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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