Re: [閒聊] 每日leetcode
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
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.7 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1730023302.A.781.html
推
10/27 18:36,
1年前
, 1F
10/27 18:36, 1F
→
10/27 19:13,
1年前
, 2F
10/27 19:13, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1054 之 1554 篇)：