线性动态规划：最大正方形

题目描述
给定一个由 '0' 和 '1' 组成的二维矩阵，找出其中只包含 '1' 的最大正方形，并返回其面积。例如，对于以下矩阵：

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

最大正方形的面积是 4（边长为 2 的正方形）。

解题过程

步骤 1：理解问题关键
正方形的定义是边长相等的矩形，且四条边均由 '1' 组成。我们需要找到面积最大的正方形。
直接暴力枚举所有可能的正方形会非常低效（O(m²n²) 时间复杂度），因此采用动态规划优化。

步骤 2：定义状态
设 dp[i][j] 表示以矩阵中第 i 行、第 j 列的元素为右下角的最大正方形的边长。

• 如果 matrix[i][j] 是 '0'，则不可能形成以它为右下角的正方形，所以 dp[i][j] = 0。
• 如果 matrix[i][j] 是 '1'，则 dp[i][j] 的值由其上方、左方、左上方的三个相邻位置的 dp 值决定。

步骤 3：状态转移方程
考虑以 (i, j) 为右下角的正方形，其边长受三个方向限制：

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

这三个位置的最小值决定了当前正方形能扩展的最大边长，因为正方形要求所有位置都是 '1'。
因此，状态转移方程为：

如果 matrix[i][j] == '1'：
    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
否则：
    dp[i][j] = 0

步骤 4：边界条件

• 当 i = 0 或 j = 0（即第一行或第一列）时，如果 matrix[i][j] == '1'，则最大正方形边长只能是 1（因为无法向左上扩展）。
• 可以直接在遍历时处理边界，避免越界。

步骤 5：计算过程示例
以题目示例矩阵为例，逐步计算 dp 表（值为边长）：

原始矩阵：

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

初始化 dp 表（尺寸同矩阵，初始可设为 0）：

第 0 行：

• dp[0][0] = 1（因为 matrix[0][0]='1'）
• dp[0][1] = 0（matrix[0][1]='0'）
• dp[0][2] = 1
• dp[0][3] = 0
• dp[0][4] = 0

第 1 行：

• dp[1][0] = 1
• dp[1][1] = 0
• dp[1][2]：左=0, 上=1, 左上=1 → min=0 → dp[1][2]=1
• dp[1][3]：左=1, 上=0, 左上=0 → min=0 → dp[1][3]=1
• dp[1][4]：左=1, 上=1, 左上=0 → min=0 → dp[1][4]=1

第 2 行：

• dp[2][0] = 1
• dp[2][1]：左=1, 上=0, 左上=0 → min=0 → dp[2][1]=1
• dp[2][2]：左=1, 上=1, 左上=1 → min=1 → dp[2][2]=2
• dp[2][3]：左=2, 上=1, 左上=1 → min=1 → dp[2][3]=2
• dp[2][4]：左=2, 上=1, 左上=1 → min=1 → dp[2][4]=2

第 3 行：

• dp[3][0] = 1
• dp[3][1] = 0
• dp[3][2] = 0
• dp[3][3]：左=0, 上=2, 左上=0 → min=0 → dp[3][3]=1
• dp[3][4] = 0

最终 dp 表：

1 0 1 0 0
1 0 1 1 1
1 1 2 2 2
1 0 0 1 0

最大边长是 2，所以最大面积是 2² = 4。

步骤 6：算法实现要点

• 遍历矩阵，按行、列顺序计算 dp[i][j]。
• 记录遍历过程中的最大边长 max_side。
• 最终返回 max_side * max_side。

复杂度分析

• 时间复杂度：O(mn)，只需遍历一次矩阵。
• 空间复杂度：O(mn)（可优化到 O(n)，只保留上一行 dp 值）。