动态规划中等1 种解法

#221最大正方形

在只包含 0 和 1 的字符矩阵中，返回全为 1 的最大正方形面积。

#矩阵#动态规划

解题主线

dp[row][column] 表示以当前位置为右下角的全 1 正方形最大边长。

当前位置为 1 时，边长由左、上、左上三个相邻状态的最小值加一决定。

第一行或第一列的 1 只能形成边长为 1 的正方形。

解法 1：右下角边长动态规划

按行扫描矩阵，以左、上、左上三个已知状态决定当前正方形边长，并维护全局最大边长。

时间复杂度

O(mn)

空间复杂度

O(mn)

221. 最大正方形 · 右下角边长动态规划

java

final class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        int maximumSide = 0;
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                if (matrix[row][column] != '1') continue;
                if (row == 0 || column == 0) {
                    dp[row][column] = 1;
                } else {
                    dp[row][column] = 1 + Math.min(
                        dp[row - 1][column - 1],
                        Math.min(dp[row - 1][column], dp[row][column - 1])
                    );
                }
                maximumSide = Math.max(maximumSide, dp[row][column]);
            }
        }
        return maximumSide * maximumSide;
    }
}

按行扫描矩阵，以左、上、左上三个已知状态决定当前正方形边长，并维护全局最大边长。

边界与易错点

最终要求面积，记录的最大边长必须平方后返回。
只有 matrix[row][column] == '1' 时才能进行状态转移。
访问 matrix[0] 前先处理 null 或空矩阵。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q221_maximalSquare_dp.java