1504. Count Submatrices With All Ones
https://leetcode.com/problems/count-submatrices-with-all-ones/
문제
풀이(Brute Force)
Example 1 예제로 설명하자면 다음과 같다.
=>(0, 0)
mat[0][0] == 1이므로 왼쪽을 확인한다. mat[0][1] != 1 이므로 멈추고 (1, 0)을 확인한다. mat[1][0] == 1이므로 아래를 확인한다. mat[2][0] == 1 이고 맨 아래까지 왔으니 합을 구한다. => 3
=>(0, 1)
mat[0][1] == 0 이므로 0을 저장한다
=>(0, 2)
mat[0][2] == 1이므로 왼쪽을 확인한다. 하지만 맨 왼쪽이므로 끝내고 아래를 확인한다. mat[1][2] == 0이므로 끝낸다. => 1
=>(1, 1)
mat[1][1] == 1이므로 왼쪽을 확인한다. mat[1][2] == 1이므로 왼쪽을 확인한다.
mat [1][3] == 0 이므로 멈추고 아래를 확인한다.
mat[2][0] == 1이므로 왼쪽을 확인한다. mat[2][1] == 1이므로 왼쪽을 확인한다.
맨 밑이므로 합을 구한다. => 4
여기서 알아야 할 것은 tmp_col인데 해당 row 바로 위에서 멈춘 tmp_col만큼 for문을 돈다.
결과(Brute Force)
풀이(DP)
dp 테이블에 width를 저장하는 것이다.
(Example 1)
(Example 2)
Example 2에서 (1,1)을 보면 왼쪽으로 1이 3개 있으므로 width는 3이 된다.
dp[1][1] = 3을 저장하는 방식이다.
BruteForce 방법에서 tmp_col을 업데이트 시켜서 바로 위 width를 넘지 않게 하였는데 dp방법에서는 최소값을 갱신시켜 더해주는 방법이다.
(Example 1)
(Example 2)
Example2에서 (1,1)을 보면 2+ min(2,3) + min(2,2) = 6이 되고
(1,2)에서는 2 + min(2, 1) = 3이 된다.
결과(DP)
