[leetcode] 221 Maximal Square(최대 정사각형 & 동적 기획)

2079 단어 LeetCode동적 기획행렬
우리가 어떤 점을 정사각형의 오른쪽 하각으로 판단할 때 가장 큰 정사각형을 판단할 때, 그 위의 위, 왼쪽과 왼쪽 위의 세 점도 반드시 어떤 정사각형의 오른쪽 하각이다. 그렇지 않으면 이 점이 오른쪽 하각의 정사각형으로 가장 큰 것은 바로 그 자신이다.이것은 정성적인 판단이다. 그러면 구체적인 최대 정사각형의 변장은?우리는 이 점이 오른쪽 아래 모서리의 정사각형의 최대 길이로 그것의 위쪽보다 많으며, 왼쪽과 왼쪽 위쪽이 오른쪽 아래 모서리의 정사각형의 길이가 1이 많다는 것을 알고 있다. 가장 좋은 것은 그것의 위쪽이고, 왼쪽과 왼쪽 위쪽이 오른쪽 아래 모서리의 정사각형의 크기가 똑같다는 것이다. 이렇게 이 점을 더하면 더욱 큰 정사각형을 구성할 수 있다.그러나 위쪽과 왼쪽 위쪽이 오른쪽 아래쪽인 정사각형의 크기가 다르면 합치면 어느 구석이 없어진다. 이럴 때는 그 세 정사각형 중 가장 작은 정사각형의 가장자리 길이를 1로 늘릴 수밖에 없다.가령 dpi가 i, j를 오른쪽 하각의 정사각형의 최대 변장을 표시한다면
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

물론 이 점이 원 행렬에서 그 자체가 0이라면 dp[i]는 틀림없이 0이다.
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int M = matrix.size(), N = matrix[0].size(), res = 0;
        vector<vector<int>> dp(M, vector<int>(N, 0));
        for (int i = 0; i < M; ++i) if (matrix[i][0] == '1') {
            dp[i][0] = 1; res = 1;
        }
        for (int j = 0; j < N; ++j) if (matrix[0][j] == '1') {
            dp[0][j] = 1; res = 1;
        }
        for (int i = 1; i < M; ++i) {
            for (int j = 1; j < N; ++j) {
                if (matrix[i][j] == '1') 
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
                res = max(res, dp[i][j]);
            }
        }
        return res * res;
    }
};
React와 Jitsi로 화상회의 만들기!
사이트 로그 가 무엇 인지, 무슨 소 용이 있 습 니까?

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage