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).

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

