DP Java with explanation


  • 0
    C

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

Log in to reply
 

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