最大正方形如何用动态规划求边长？为什么取左、上、左上三者最小值？

简化版

最大正方形用 dp[i][j] 表示以 (i,j) 为右下角的全 1 正方形最大边长。若当前格是 1，则 dp[i][j] = min(上, 左, 左上) + 1；若当前格是 0，则为 0。答案是最大边长的平方。

详细版

一个以 (i,j) 为右下角的正方形要扩展一圈，必须同时满足上方、左方、左上方三个方向都能支撑相同边长。因此当前边长由三者最小值决定。使用多一行多一列的哨兵数组可以避免边界判断。

遍历矩阵每个格子，若 matrix[i-1][j-1] == '1'，转移为 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。时间复杂度 O(mn)，空间复杂度 O(mn)，可优化到 O(n)。

完整版教学

一、状态为什么定义为“右下角”

正方形需要确定位置和大小。如果只说“到当前位置为止最大正方形”，很难转移；定义成“以当前位置为右下角”后，当前格是否能扩展只和左、上、左上有关。

? ? ?
? □ □
? □ X

X 是右下角

dp[i][j] 表示以 X 为右下角的最大正方形边长。

二、为什么当前格必须是 1

如果当前格是 0，它不可能作为全 1 正方形的右下角，dp[i][j]=0。如果当前格是 1，至少能形成边长为 1 的正方形，再看能否向左上扩展。

记忆钩子：矩阵 DP 先问当前格能不能作为答案的一部分，再问能扩多大。

三、为什么取三者最小值

要形成边长为 k 的正方形，左边、上边和左上内部都必须足够大：

依赖	作用
上 `dp[i-1][j]`	支撑右侧竖边上方
左 `dp[i][j-1]`	支撑底边左侧
左上 `dp[i-1][j-1]`	支撑内部正方形

如果其中最小值是 2，那么当前最多扩成边长 3；如果某个方向只有 1，其他方向再大也只能扩成 2。

四、公式推导

当前格为 1 时：

dp[i][j] = min(
  dp[i-1][j],
  dp[i][j-1],
  dp[i-1][j-1]
) + 1

当前格为 0 时：

dp[i][j] = 0

最终题目要求面积，所以返回 maxSide * maxSide，不要忘记平方。

五、代码模板

int maximalSquare(char[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    int[][] dp = new int[m + 1][n + 1];
    int maxSide = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (matrix[i - 1][j - 1] == '1') {
                dp[i][j] = Math.min(dp[i - 1][j],
                           Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }
    return maxSide * maxSide;
}

多开一行一列后，第一行和第一列天然是 0，边界格也能使用统一公式。

六、用数字矩阵走一遍

考虑局部状态：

上    = 2
左    = 3
左上  = 2
当前格 = 1

当前边长是 min(2,3,2)+1 = 3。虽然左边能支持 4 的宽度，但上和左上只能支持到 3，所以不能更大。

七、常见误区与追问

误区：返回最大边长。 题目要求面积，要返回 maxSide * maxSide。
误区：只看左和上。 缺少左上会误判内部是否全为 1。
误区：把字符 '1' 当数字 1 比较。 Java 中矩阵常是 char[][]，要比较 '1'。
追问：为什么用右下角定义？ 这样扩展正方形只依赖已计算的左、上、左上。
追问：空间能优化吗？ 可以按行滚动到一维，但要保存旧的左上值。
追问：最大矩形能用同样公式吗？ 不能，最大矩形通常转成柱状图单调栈。

八、加强记忆

最大正方形的核心图像是“当前格做右下角，能不能往左上扩一圈”。当前格为 0 就归零；当前格为 1 时，左、上、左上三个邻居都要支撑扩展，所以取最小值加 1。最后别忘了题目要面积不是边长。用哨兵行列统一边界，是写代码时最稳的做法。

简化版

详细版