day-37 最大正方形

思路
动态规划，这题主要得弄明白状态转换方程，dp[i][j]表示以（i,j）为右下角的最大正方形

解题方法
1.首先将第一行和第一列初始化，当对应位置的matrix为'0'时，dp数组对应位置也为零，否则为1
2.对剩下其他位置进行遍历，若对应位置的matrix为'0'时，dp数组对应位置也为零，若不为'0'，则为dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1
3.最后dp数组中最大值的平方即为答案

Code

class Solution {

    public int maximalSquare(char[][] matrix) {

        int ans=0;
        int row=matrix.length;
        int cols=matrix[0].length;
        int arr[][]=new int[row][cols];
        for(int i=0;i<row;i++){

            if(matrix[i][0]=='0')arr[i][0]=0;
            else{

                arr[i][0]=1;
                ans=1;
                }
        }
        for(int i=0;i<cols;i++){

            if(matrix[0][i]=='0')arr[0][i]=0;
            else{

                arr[0][i]=1;
                ans=1;
            } 
        }
        for(int i=1;i<row;i++){

            for(int j=1;j<cols;j++){

                if(matrix[i][j]=='0'){

                    arr[i][j]=0;
                }else{

                    arr[i][j]=arr[i][j]=Math.min(arr[i-1][j],Math.min(arr[i-1][j-1],arr[i][j-1]))+1;
                }
                ans=Math.max(arr[i][j],ans);
            }
        }
        return ans*ans;
    }
}

原文链接: https://blog.csdn.net/qq_53568730/article/details/139398353

目录