subject ：

In a '0' and '1' In the two-dimensional matrix , Found contains only '1' The largest square of , And return its area .

Answer key ：

dp Specific definition ：dp[i + 1][j + 1] Express 「 By the end of i That's ok 、 The first j The maximum side length of the square listed as the lower right corner 」
Why not dp[i][j]

Any square , We all 「 rely on 」 Current grid Left 、 On 、 The situation of the upper left three squares , But the upper layer of the first row has no grid , There is no grid on the left of the first column , Need to do special if Deal with it by judgment , For code simplicity , We Suppose to add One more line '0'、 One more train, all '0'

here dp The size of the array is also specified as new dp[height + 1][width + 1]
The initial value is to put the first column dp[row][0] 、 first line dp[0][col] All Fu Wei 0, The first line is equivalent to all calculations 、 In the first column dp value
The title requires an area of . according to 「 area = Side length x Side length 」 You know , We just need to figure out Maximum side length that will do
Definition maxSide Indicates the longest side length , One at a time dp, Just maxSide = max(maxSide, dp);
Eventually return return maxSide * maxSide;

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length < 1 || matrix[0].length < 0) {
            return 0;
        }
        int h = matrix.length;
        int w = matrix[0].length;
        int maxLen = 0;
        int[][] dp = new int[h + 1][w + 1]; //  It is equivalent to adding the first line after preprocessing 、 The first column is 0
        for (int i = 0 ; i < h; i++) { // Traverse matrix
            for (int j = 0; j < w; j++) {
                if (matrix[i][j] == '1') {
                    // Take the left 、 On the right 、 The minimum length at the top left plus the current cell length 1
                    // Pay attention to the left 、 On the right 、 Top left is [i + 1][j + 1] Benchmarking , instead of [i][j]
                    dp[i + 1][j + 1] = Math.min(Math.min(dp[i + 1][j], dp[i][j + 1]), dp[i][j]) + 1; 
                }
                maxLen = Math.max(maxLen, dp[i + 1][j + 1]);
            }
        } 
        return maxLen * maxLen;
    }
}

Reference resources ： Power button