Maximal Square (leetcode 221, lintcode 436)

중점:matrix[i][j]==1일 때만 상태 방정식을 업데이트하려면 건너뛰는 것은 0이다.
또한 [row+1] [col+1]의 방법으로 실현할 수 있으며 [0][0]를 0으로 초기화하여 코드를 간결하게 할 수 있다.

     int maximalSquare(vector>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return 0;
        int row = matrix.size(), col = matrix[0].size();
        
        vector> dp(row+1, vector(col+1, 0));
        
        int max_len = 0;
        for(int i=1; i<=row; i++){
            for(int j=1; j<=col; j++){
                if(matrix[i-1][j-1] == '1'){
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
                    max_len = max(max_len, dp[i][j]);
                }
            }
        }
        return max_len * max_len;
    }

sliding array to further reduce space complexity: 스크롤 그룹의 최적화: 스크롤 그룹은 all row and all column을 초기화하지 못하기 때문에 matrix[i][j]=0 시 건너뛸 수 없습니다. dp[i][j]를 0으로 설정하십시오.

class Solution {
public:
    /**
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
    int maxSquare(vector > &matrix) {
        // write your code here
        if(matrix.empty() || matrix[0].empty()) return 0;
        int row = matrix.size(), col = matrix[0].size();
        vector> dp(2, vector(col+1, 0));
        
        int max_len = 0;
        for(int i=1; i<=row; i++){
            for(int j=1; j<=col; j++){
                if(matrix[i-1][j-1] == 1){
                    dp[i%2][j] = min(dp[(i-1)%2][j-1], min(dp[(i-1)%2][j], dp[i%2][j-1])) + 1;
                    if(dp[i%2][j] > max_len) max_len = dp[i%2][j];
                }else{
                    dp[i%2][j] = 0;
                }
                
            }
        }
        return max_len * max_len;
    }
};