LeetCode 1277: Count Square Submatrices With All Ones ·

基本資料
#

難易度: medium 第一次嘗試：2026-07-04 來源：Day 32 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

LC 1277: pass after state-definition repair
explain LC 1277 using the same local square state as LC 221, but with sum(dp) as the final aggregation

當天筆記摘錄
#

Problem 2 - LC 1277 Count Square Submatrices With All Ones
#

Pattern: 2D DP on square geometry with count aggregation.

Why This Fits
#

This is the same local square-growth logic as LC 221, but the question changed from:

what is the largest square?

to:

how many all-1 squares exist in total?

So the state can stay almost the same, but the final aggregation changes.

Core State / Invariant
#

dp[r][c] = side length of the largest all-1 square whose bottom-right corner is (r, c)

Transition
#

If matrix[r][c] == 0:

dp[r][c] = 0

If matrix[r][c] == 1 and not on the first row or first column:

dp[r][c] = 1 + min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])

Boundary 1 cells contribute:

dp[r][c] = 1

Why Summing DP Works
#

If dp[r][c] = k, then that cell is the bottom-right corner of:

one 1 x 1 square
one 2 x 2 square
…
one k x k square

So each dp[r][c] contributes exactly k valid squares to the final count.

Final Answer
#

answer = sum(dp[r][c] for all cells)

Complexity
#

Time: O(m * n)
Space: O(m * n)

Can be compressed to:

Space: O(n)

Common Mistakes
#

reusing the LC 221 state but still returning only the max
forgetting that each side length contributes multiple squares
using max(...) instead of min(...)
not being able to explain why summing side lengths is valid

Strong Spoken Explanation
#

I reuse the same DP state as LC 221: dp[r][c] is the side length of the largest all-1 square ending at (r, c). The recurrence stays the same because square growth still depends on top, left, and diagonal. The difference is the output: if a cell has largest side length k, it contributes k different valid squares ending there, so I sum all DP values instead of tracking only the maximum.

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from typing import List

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * (n + 1)
        total = 0

        for r in range(1, m + 1):
            prev_diag = 0
            for c in range(1, n + 1):
                old = dp[c]
                if matrix[r - 1][c - 1] == 1:
                    dp[c] = 1 + min(dp[c], dp[c - 1], prev_diag)
                    total += dp[c]
                else:
                    dp[c] = 0
                prev_diag = old

        return total