[Leetcode] 221 Maximum square

Dynamic programming + square, a more typical shape

/ / pseudo code
if (matrix(i - 1, j - 1) = ='1') {
    dp(i, j) = min(dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)) + 1;
}
Copy the code

Where, dp(I, j) takes matrix(i-1, J-1) as the maximum side length of the square in the lower right corner. Is equivalent to: dp(I + 1, j + 1) is the maximum side length of the square with matrix(I, j) as the lower right corner

reference

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix==null||matrix.length<1||matrix[0].length<1) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m+1][n+1];
        int max = 0;
        for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(matrix[i][j]=='1'){
                    dp[i+1][j+1] = Math.min(Math.min(dp[i][j+1],dp[i+1][j]),dp[i][j])+1;
                    max = Math.max(max,dp[i+1][j+1]); }}}returnmax*max; }}Copy the code