【动态规划】221. 最大正方形

221. 最大正方形

解题思路

• 参考题解：https://leetcode.cn/problems/maximal-square/solutions/44586/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/?show=1
• 主要思想：选择左边 上面 左上方 最小的值，dp[i+1][j+1]代表以第i行 第j列为右下角的正方形的最大边长

class Solution {
    public int maximalSquare(char[][] matrix) {
        // BASE CASE 没有元素的情况
        if(matrix == null || matrix.length < 1 || matrix[0].length < 1){
            return 0;
        }

        int height = matrix.length;
        int width = matrix[0].length;
        int maxSide = 0;


        // 新增一行 一列  全部都是0
        int[][] dp = new int[height + 1][width + 1];

        // dp[i+1][j + 1]表示 以第i行 第j列为右下角的正方形的最大边长
        // dp[1][1] 表示以(0,0)为右下角边界的正方形的最大边长


        for(int row = 0; row < height; row++){
            for(int col = 0; col < width; col++){
                if(matrix[row][col] == '1'){
                    dp[row + 1][col + 1] = Math.min(Math.min(dp[row + 1][col],dp[row][col+1]),dp[row][col]) + 1;
                    maxSide = Math.max(maxSide,dp[row+1][col+1]);
                }
            }
        }

        return maxSide * maxSide;
    }
}