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;}
}