모두 1인 정사각형 부분행렬 계산

1277. 모두 일수로 정사각형 부분행렬 계산하기

난이도:중

주제: 배열, 동적 프로그래밍, 매트릭스

1과 0으로 구성된 m * n 행렬이 주어지면 모두 1을 갖는 정사각형 하위 행렬의 수를 반환합니다.

예 1:

• 입력: 행렬 = [[0,1,1,1], [1,1,1,1], [0,1,1,1]]
• 출력: 15
• 설명:
  • 1변의 정사각형이 10개 있습니다.
  • 변 2의 정사각형이 4개 있습니다.
  • 3번 변의 정사각형 1개가 있습니다.
  • 총 정사각형 수 = 10 4 1 = 15.

예 2:

• 입력: 행렬 = [[1,0,1], [1,1,0], [1,1,0]]
• 출력: 7
• 설명:
  • 1변의 정사각형은 6개입니다.
  • 2변 1칸이 있습니다.
  • 총 정사각형 수 = 6 1 = 7.

제약조건:

• 1
• 1
• 0

힌트:

1. 위 모서리가 (0,0)인 부분행렬 요소의 합을 계산하는 덧셈 테이블을 만듭니다.
2. O(n3)의 모든 ^{하위 사각형}을 반복하고 합계가 전체 배열을 1로 만드는지 확인하고, 확인되면 답에 1을 추가합니다.

해결책:

동적 계획법(DP)을 사용하면 행렬의 각 셀에서 끝날 수 있는 모든 정사각형 하위 행렬의 수를 추적할 수 있습니다. 이를 달성하기 위한 접근 방식은 다음과 같습니다.

1. DP 매트릭스 정의:

   • DP 행렬 dp를 정의합니다. 여기서 dp[i][j]는 셀(i, j)에 오른쪽 하단 모서리가 있는 가장 큰 정사각형 부분 행렬의 크기를 나타냅니다.

2. 전환 공식:

   • 행렬의 각 셀(i, j)에 대해:

     • 행렬[i][j]가 1인 경우 dp[i][j]의 값은 (i-1, j), (i, j)에서 확장하여 형성할 수 있는 제곱의 최소값에 따라 달라집니다. -1) 및 (i-1, j-1). 전환 공식은 다음과 같습니다.

     dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
     

  - If `matrix[i][j]` is 0, `dp[i][j]` will be 0 because a square of ones cannot end at a cell with a zero.

1. 모든 사각형을 센다:

   • 모든 (i, j)에 대해 dp[i][j] 값을 누적하여 모든 크기의 총 제곱 수를 구합니다.

2. 시간 복잡성:

   • 이 솔루션은 O(m X n)에서 작동합니다. 여기서 m 및 n는 행렬의 차원입니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 1277. 모두 일수로 정사각형 부분행렬 계산하기

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

설명:

1. 각 위치(i, j)에서 끝나는 가장 큰 정사각형 부분행렬의 크기를 추적하기 위해 2D 배열 dp를 초기화합니다.
2. 행렬의 각 셀에 대해:
   • 셀에 1이 있는 경우 인접 셀을 기반으로 dp[i][j]를 계산하고 해당 값을 totalSquares에 추가합니다.
3. 마지막으로 totalSquares에는 모든 정사각형 하위 행렬의 개수가 모두 1로 포함됩니다.

이 솔루션은 효율적이며 문제에 제공된 제약 조건을 충족합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 모두 1인 정사각형 부분행렬 계산의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!