Re: [閒聊] 每日leetcode

作者: dont   2024-10-27 18:01:39
1277. Count Square Submatrices with All Ones
## 思路
DP
matrix[r][c] = 右下角為(r, c)的正方形個數
1 + min(matrix[r-1][c-1], matrix[r][c-1], matrix[r-1][c])
更新matrix並加總
## Code
```python
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
len_r, len_c = len(matrix), len(matrix[0])
res = 0
for r in range(len_r):
for c in range(len_c):
if r and c and matrix[r][c]:
matrix[r][c] = 1 + min(matrix[r-1][c-1], matrix[r-1][c],
matrix[r][c-1])
res += matrix[r][c]
return res
```

Links booklink

Contact Us: admin [ a t ] ucptt.com