发表于 2024.07.16

• 通过观察发现，如果一个正方形子矩阵的右下角是(i, j)，且边长为k，那么这个该正方形包含四个重叠的、边长为k - 1的正方形子矩阵，分别以(i - 1, j - 1)、(i - 1, j)、(i, j - 1)、(i, j)为右下角。

  因此，我们可以定义dp[i][j]为以(i, j)为右下角的正方形子矩阵的最大边长，那么有状态转移方程dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1(如果matrix[i][j] == 1，否则为0)。最后，答案即为所有dp[i][j]的和。

  class Solution:
      def countSquares(self, matrix: List[List[int]]) -> int:
          m, n = len(matrix), len(matrix[0])
          ans = 0
          dp = [[0] * n for _ in range(m)]
          for i in range(m):
              for j in range(n):
                  if not matrix[i][j]:
                      continue
                  dp[i][j] = min(
                      dp[i - 1][j] if i > 0 else 0,  # 要注意边界条件, 下同
                      dp[i][j - 1] if j > 0 else 0,
                      dp[i - 1][j - 1] if i > 0 and j > 0 else 0
                  ) + 1
                  ans += dp[i][j]
          return ans

• LC 题目链接