线性动态规划：统计全为1的正方形子矩阵

题目描述：
给定一个 m × n 的二进制矩阵（只包含0和1），统计其中全由1组成的正方形子矩阵的个数。

例如，对于矩阵：

[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]

总共有15个全1正方形子矩阵：

• 10个1×1的正方形
• 4个2×2的正方形
• 1个3×3的正方形

解题过程：

步骤1：理解问题本质
我们需要统计所有可能的正方形子矩阵，这些子矩阵必须全部由1组成。正方形的边长可以从1到min(m,n)。

步骤2：定义状态
定义dp[i][j]表示以(i,j)为右下角顶点的最大正方形边长。这个定义很关键，因为：

• 如果以(i,j)为右下角的正方形边长为k，那么它同时包含了边长为1,2,...,k的k个正方形
• 因此dp[i][j]的值直接告诉我们以(i,j)为右下角的正方形个数

步骤3：状态转移方程
对于位置(i,j)：

• 如果matrix[i][j] = 0，那么dp[i][j] = 0（不能形成正方形）
• 如果matrix[i][j] = 1，那么：
  dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

为什么这样转移？
考虑以(i,j)为右下角的正方形，它的最大边长受限于：

1. 上方(i-1,j)位置的最大正方形边长
2. 左方(i,j-1)位置的最大正方形边长
3. 左上方(i-1,j-1)位置的最大正方形边长

取三者最小值再加1，确保能形成一个完整的正方形。

步骤4：初始化

• 对于第一行(i=0)：dp[0][j] = matrix[0][j]（只能是0或1）
• 对于第一列(j=0)：dp[i][0] = matrix[i][0]（只能是0或1）

步骤5：计算总个数
总正方形个数 = 所有dp[i][j]值的总和
因为dp[i][j] = k意味着有k个以(i,j)为右下角的正方形（边长分别为1,2,...,k）

步骤6：完整算法实现

def countSquares(matrix):
    if not matrix or not matrix[0]:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    total = 0
    
    # 初始化第一行和第一列
    for i in range(m):
        dp[i][0] = matrix[i][0]
        total += dp[i][0]
    
    for j in range(1, n):  # 避免重复计算(0,0)
        dp[0][j] = matrix[0][j]
        total += dp[0][j]
    
    # 填充dp表
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 1:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                total += dp[i][j]
    
    return total

步骤7：示例推演
以前面的例子推演：

矩阵：
[0,1,1,1]
[1,1,1,1]  
[0,1,1,1]

dp表：
[0,1,1,1]
[1,1,2,2]
[0,1,2,3]

计算过程：
- (0,0): 0
- (0,1): 1
- (0,2): 1  
- (0,3): 1
- (1,0): 1
- (1,1): min(1,1,0)+1 = 1
- (1,2): min(1,1,1)+1 = 2
- (1,3): min(1,2,1)+1 = 2
- (2,0): 0
- (2,1): min(0,1,1)+1 = 1  
- (2,2): min(1,2,2)+1 = 2
- (2,3): min(2,2,2)+1 = 3

总和 = 0+1+1+1 + 1+1+2+2 + 0+1+2+3 = 15

步骤8：复杂度分析

• 时间复杂度：O(m×n)，遍历整个矩阵一次
• 空间复杂度：O(m×n)，用于存储dp表

这个解法巧妙地利用动态规划，在计算最大正方形边长的同时统计了所有可能的正方形个数，是典型的线性动态规划应用。