# DP Java with explanation

• dp status equation:

``````   dp[i][j]  -> longest length to construct square.
``````

dp status transition equation:

``````   dp(i,j) =
if(matrix(i,j) == 0) no possible square can be constructed. value is 0
if(matrix(i,j) == 1)
check up: dp[i-1][j]
check left: dp[i][j-1]
check diagonal: dp[i-1][j-1]
the largest length would be: min(left,up,diagonal) + 1

Optimization: rolling array to save space.  I saved the bother to implement that.
Time complexity: O(mn)
Space complexity: O(mn), Rolling array: O(N) where n is cols.
``````
``````public int maximalSquare(char[][] matrix) {
if(matrix==null || matrix.length ==0) return 0;
int max = 0;
int row = matrix.length, col = matrix[0].length;
int[][] dp = new int[row+1][col+1];
for(int i=1;i<=row;i++){
for(int j =1;j<=col;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;
max = Math.max(max,dp[i][j]);
}
}
}
return max*max;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.