public int maximalSquare(char[][] matrix){
  if (matrix == null) {
    return 0;
  }
  int r=matrix.length;
  int c=r == 0 ? 0 : matrix[0].length;
  int[][] dp=new int[r + 1][c + 1];
  int maxLen=0;
  for (int i=1; i <= r; i++) {
    for (int j=1; j <= c; j++) {
      if (matrix[i - 1][j - 1] == '1') {
        dp[i][j]=Math.min(Math.min(dp[i - 1][j],dp[i][j - 1]),dp[i - 1][j - 1]) + 1;
        maxLen=Math.max(maxLen,dp[i][j]);
      }
    }
  }
  return maxLen * maxLen;
}

public int maximalSquare ( char [ ] [ ] matrix ) { if ( matrix == null ) { return 0 ; } int r = matrix . length ; int c = r == 0 ? 0 : matrix [ 0 ] . length ; int [ ] [ ] dp = new int [ r + 1 ] [ c + 1 ] ; int maxLen = 0 ; for ( int i = 1 ; i <= r ; i ++ ) { for ( int j = 1 ; j <= c ; j ++ ) { if ( matrix [ i - 1 ] [ j - 1 ] == '1' ) { dp [ i ] [ j ] = Math . min ( Math . min ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) , dp [ i - 1 ] [ j - 1 ] ) + 1 ; maxLen = Math . max ( maxLen , dp [ i ] [ j ] ) ; } } } return maxLen * maxLen ; }
dp , 2d matrix . the recurrence relation here is not easy to see . use largest square ' s edge length formed including current grid . if the current grid is an 1 , the edge length of current grid is the ( minimum of its top , top - left , and left ) + 1 . otherwise , if its 0 , the edge length is still zero .
