public int maximalSquare(char[][] a) {
if(a.length == 0) return 0;
int m = a.length, n = a[0].length, result = 0;
int[][] b = new int[m+1][n+1];
for (int i = 1 ; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if(a[i1][j1] == '1') {
b[i][j] = Math.min(Math.min(b[i][j1] , b[i1][j1]), b[i1][j]) + 1;
result = Math.max(b[i][j], result); // update result
}
}
}
return result*result;
}
Extremely Simple Java Solution :)


Logic :
Top, Left, and Top Left decides the size of the square. If all of them are same, then the size of square increases by 1. If they're not same, they can increase by 1 to the minimal square. If you take an example and work it out, it'll be much easier to understand when it comes to dynamic programing. :)

Nice! I happen to find this too. Making dp[i][j] represents state of matrix[i1][j1] could save the trouble of boundary initialization. Not sure if this is a general trick for all 2d DP problems or only works in some special case?
ps: I think this is general for problems such as what's the max, longest XXX and so on where leaving buffer region 0 is ok. But it doesn't work in "min" case which will be wrong if you Math.min(min, 0).

dp[i][j] 代表在以
i, j
这一格为右下角的正方形边长。
如果这一格的值也是1
，那这个正方形的边长就是他的上面，左手边，和斜上的值的最小边长 +1。因为如果有一边短了缺了，都构成不了正方形。
class Solution { public int maximalSquare(char[][] matrix) { if(matrix.length == 0) return 0; int m = matrix.length, n = matrix[0].length; int[][] dp = new int[m + 1][n + 1]; int maxEdge = 0; for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; 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; maxEdge = Math.max(maxEdge, dp[i][j]); } } } return maxEdge * maxEdge; } }

pretty the same except starting index
public int maximalSquare(char[][] matrix) { if (matrix == null  matrix.length == 0) { return 0; } int row = matrix.length, col = matrix[0].length; int[][] dp = new int[row][col]; int len = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { int value = matrix[i][j]  '0'; if (value == 0) continue; if (i == 0  j == 0) { dp[i][j] = value; } else { dp[i][j] = Math.min(dp[i  1][j], Math.min(dp[i][j  1], dp[i  1][j  1])) + 1; } len = Math.max(len, dp[i][j]); } } return len * len; }

Same idea, but using O(n) space complexity rathen than O(mn)
public class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null  matrix.length == 0  matrix[0].length == 0) return 0; int m = matrix.length; int n = matrix[0].length; int max = 0; //initialization int[][] dp = new int[2][n+1]; for(int i = 1; i <= m ; i++){ for(int j = 1; j <= n; j++){ if(matrix[i1][j1] == '0') { dp[i%2][j] = 0; }else{ dp[i%2][j] = Math.min( Math.min(dp[(i+1)%2][j1], dp[(i+1)%2][j]) , dp[i%2][j1]) + 1; } max = dp[i%2][j] > max ? dp[i%2][j] : max; } } return max*max; } }

