# Leetcode 221. Maximal Square
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/maximal-square/ 。

想法 :

最大正方形DP。
if(這一格是1)
area[i][j] = min(area[i-1][j], area[i-1][j-1], area[i][j-1]) + 1;

時間複雜度 : O(r*c)。

程式碼 :

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int r=matrix.size(), c=matrix[0].size(), ans=0, dp[310][310]={0};
        
        for(int i=0 ; i<=r ; i++){
            for(int j=0 ; j<=c ; j++){
                dp[i][j]=0;
            }
        }
        
        for(int i=1 ; i<=r ; i++){
            for(int j=1 ; j<=c ; 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;
                    ans=max(ans, dp[i][j]);
                }
            }
        }
        
        return ans * ans;
    }
};