Python을 사용하여 모든 부분 행렬을 계산하는 프로그램

<시간/>

m x n 이진 행렬이 있다고 가정하고 모두 1인 부분행렬의 수를 찾아야 합니다.

따라서 입력이 다음과 같으면

1	0	1
0	1	1
0	1	1

6(1x1) 행렬, 3(2,1) 행렬, 2(1x2) 행렬, 1(3x1) 행렬 및 1(4x4) 행렬이 있으므로 출력은 13이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m :=행렬의 행 수
n :=행렬의 열 개수
dp :=같은 크기의 0 행렬 m x n
0 ~ m - 1 범위의 i에 대해 수행
- 0 ~ n - 1 범위의 j에 대해 수행
  - i가 0 및 행렬[i, j]과 같으면
    - dp[i, j] :=1
  - 그렇지 않으면 행렬[i][j]가 0이 아닌 경우
    - dp[i, j] :=dp[i-1, j] + 1
총계 :=0
0 ~ m - 1 범위의 i에 대해 수행
- 0 ~ n - 1 범위의 j에 대해 수행
  - j+1에서 n 사이의 k에 대해 수행
    - 총계 :=총계 + 최소 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