题目描述

题解

动态规划

题目要求二维矩阵中的最大正方形, 因为各个元素之间有着比较强的联系, 所以可以使用动态规划的方法做.

刚开始定义的dp[i][j] 含义为以(i, j)结尾时的最大正方形面积, 但是相邻元素间很难直观找出面积关系, 相比之下最大的正方形边长较为明显.

状态定义:

dp[i][j] 定义为以(i,j)结尾的最大正方形边长.

状态转移:

如果当前位置的元素为0, 那么不能构成正方形, 那么dp[i][j]=0

如果当前位置的元素为1, 要么该点单独构成一个边长为1的正方形, 要么与周围的元素构成一个更大的正方形.具体的值由以下状态转移关系决定:

1	dp[i][j] = min(左边的dp值, 上边的dp值, 斜上方的dp值) +1

输出:

更新dp数组时不断记录当前的最大正方形边长, 最后将最大边长的平方输出即可

public int maximalSquare(char[][] matrix) {
    if (matrix.length == 0) {
        return 0;
    }

    int row = matrix.length;
    int col = matrix[0].length;
    int res = 0;
    int[][] dp = new int[row + 1][col + 1];
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; 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;
                res = Math.max(res, dp[i][j]);
            }
        }
    }

    return res * res;
}