lc 221. 最大正方形

本题我也能很快的想到用dp，dp[i][j]表示以[i,j]为右下角的最大正方形的边长

但是在递推的时候，没有想到直接利用之前的计算的办法，当时想的是除了dp[i-1][j-1]，就是看(i,j)左边和上边为1的个数

但是实际上可以利用dp[i-1][j],dp[i][j-1]

参考：

https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/

class Solution { // dp[i][j]表示以[i,j]为右下角的最大正方形的面积 public int maximalSquare(char[][] matrix) { if(matrix==null||matrix.length==0||matrix[0].length==0){ return 0; } int[][] dp=new int[matrix.length][matrix[0].length]; int max=0; for(int i=0;i<dp.length;i++){ for(int j=0;j<dp[0].length;j++){ if(i==0||j==0){ dp[i][j]=matrix[i][j]=='1'?1:0; }else{ if(matrix[i][j]!='1'){ dp[i][j]=0; }else dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1; } max=Math.max(max,dp[i][j]); } } return max*max; } }