question: 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 ; }
target:  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.