[2024] Day28. 1074. Number of Submatrices That Sum to Target

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 28일 (일)
Leetcode daily problem

1074. Number of Submatrices That Sum to Target

https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/description/?envType=daily-question&envId=2024-01-28

Problem

정수 matrix와 target이 주어질 떄
target까지의 비어 있지 않은 부분행렬의 수의 합을 반환한다.

부분행렬 x1, y1, x2, y2는 x1 <= x <= x2 및 y1 <= y <= y2인 모든 셀 행렬[x][y]의 집합이다. 두 부분행렬(x1, y1, x2, y2)과 (x1', y1', x2', y2')는 서로 다른 좌표가 있는 경우 서로 다르다(예: x1 != x1'인 경우).

Solution

dynamic programming

Code

Complexicity

시간 복잡도

공간 복잡도

---