My Java DP AC solution simple and easy to understand with explanation


  • 18
    P

    It's actually to keep recording the max n*n window at each cell of the matrix.
    At each cell, we define that the dynamic programming status at that cell is - if I am the most right-bottom guy of a square, how big the square I can build. With this definition, this status will be transferrable to the guys, right, below, and right below me.

     public class Solution {
            public int maximalSquare(char[][] matrix) {
                
                //illegal check - no square can be formed
                if(matrix == null || matrix.length == 0) return 0;
                
                int result = 0;
                int[][] count = new int[matrix.length][matrix[0].length];
                
                //initialize first row and first column
                for(int i = 0; i < matrix.length; i ++) {
                    count[i][0] = matrix[i][0] == '0' ? 0 : 1;
                    result = Math.max(result, count[i][0]);
                }
                
                for(int i = 0; i < matrix[0].length; i ++) {
                    count[0][i] = matrix[0][i] == '0' ? 0 : 1;
                    result = Math.max(result, count[0][i]);
                }
                
                //start to transfer status to iterate each cell from (1, 1) to (m, n)
                //if i am a 0, the square stops, reset
                for(int i = 1; i < matrix.length; i++) {
                    for(int j = 1; j < matrix[0].length; j++) {
                        
                        //I break the square reset myself to zero
                        if(matrix[i][j] == '0') {
                            count[i][j] = 0;
                            continue;
                        }
                        
                        //if I am 1, it depends if I can grow the size of the square, if I have a 0 guy around me, 
                        //I can only be a top left guy
                        if(count[i - 1][j - 1] == 0 || count[i - 1][j] == 0 || count[i][j - 1] == 0) {
                            count[i][j] = 1;
                        }
                        //if guys around are the same size, I can be the right-bottom guy of a bigger square
                        else if(count[i - 1][j - 1] == count[i - 1][j] && count[i - 1][j] == count[i][j - 1]) {
                            count[i][j] = count[i - 1][j - 1] + 1;
                        }
                        //guys around me not the same, I can only be the right-bottom guy of a least square
                        else {
                            count[i][j] = Math.min(Math.min(count[i - 1][j - 1], count[i - 1][j]), 
                                                                                  count[i][j - 1]) + 1;
                        }
                        result = Math.max(result, count[i][j]);
                    }
                }
                return result * result;
            }
        }
    

    Of course, the last three if-else condition can be entirely removed by this line of code:
    Math.min(Math.min(count[i - 1][j - 1], count[i - 1][j]), count[i][j - 1]) + 1, because it covers all situations we can think of.

    public class Solution {
        public int maximalSquare(char[][] matrix) {
            
            if(matrix == null || matrix.length == 0) return 0;
            
            int result = 0;
            int[][] count = new int[matrix.length][matrix[0].length];
            
            for(int i = 0; i < matrix.length; i ++) {
                count[i][0] = matrix[i][0] == '0' ? 0 : 1;
                result = Math.max(result, count[i][0]);
            }
            
            for(int i = 0; i < matrix[0].length; i ++) {
                count[0][i] = matrix[0][i] == '0' ? 0 : 1;
                result = Math.max(result, count[0][i]);
            }
            
            
            for(int i = 1; i < matrix.length; i++) {
                for(int j = 1; j < matrix[0].length; j++) {
                    
                    if(matrix[i][j] == '0') {
                        count[i][j] = 0;
                        continue;
                    }
                    
                    count[i][j] = Math.min(Math.min(count[i - 1][j - 1], count[i - 1][j]), 
                                                                          count[i][j - 1]) + 1;
                    result = Math.max(result, count[i][j]);
                }
            }
            return result * result;
        }
    }
    

    But by breaking into the situation into sub pieces will help my think cautiously.

    In addition, the space O(n^2) can be possibly downgraded to O(n) or even O(1) with 3 pointers to the current value of guys to my left, left-above, and above, if needed.


  • 1
    M

    Nice solution. For some reason I have problems finding DP solutions. Any tipps how to approach them? For space efficiency I would just reuse the original array and handle math with (myChar - '0') if you know what I mean. ('1' - '0' will be 1, '2' - '0' will be 2 etc.)


  • 0
    P

    Usually DP problems have very similar logistics.(e.g. finding maximum/minimum something, and you can't do any sorting thing to re-frame the question - that is, results are accumulative). so whenever you feel that, the problem looks like in this way, they are usually DP problem.

    In addition, if you can picture the problem on a either 1 or 2 dimension array, typically it's DP problem. When you do more practices, you can feel it.

    Good luck!


  • 0
    G

    Thanks for the lucid explanation, @Preston0411 . Sometimes, I wish there were more posts that gave a clear understanding like the way you've explained in simple terms.


Log in to reply
 

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