###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 221. Maximal Square

## [題目連結:] https://leetcode.com/problems/maximal-square/description/

## 題目:
Given an ```m x n``` binary ```matrix``` filled with ```0```'s and ```1```'s, find the largest square containing only ```1```'s and return its area.


## 解題想法:
* 此題為求最大的正方形面積(由全"1"構成)

* dp:
* dp[i][j]表示:達到位置(i,j)能組成的最大正方形**邊長**
* 初始所需:

    res=0
    m=len(matrix)
    n=len(matrix[0])
    dp=[[0 for _ in range(n)] for _ in range(m)]

* 初始化邊界:上邊界、左邊界

    #init
    for i in range(m):
        if matrix[i][0]=='1':
            dp[i][0]=1
            res=1 #res為最終return 
    for j in range(n):
        if matrix[0][j]=='1':
            dp[0][j]=1
            res=1

* 對於當前dp[i][j]:
* 遇到matrix[i][j]==1才要注意，否則該dp[i][j]依舊保持0
* matrix[i][j]=='1':
* dp[i][j]為求右下角，判斷依據為: **左上、上、左 取最小值+1

## Python:

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        res=0
        m=len(matrix)
        n=len(matrix[0])
        dp=[[0 for _ in range(n)] for _ in range(m)]
        #init
        for i in range(m):
            if matrix[i][0]=='1':
                dp[i][0]=1
                res=1
        for j in range(n):
            if matrix[0][j]=='1':
                dp[0][j]=1
                res=1
        #dp
        for i in range(1,m):
            for j in range(1,n):
                #遇到matrix[i][j]==1才要注意 否則該dp[i][j]依舊保持0
                if matrix[i][j]=='1':
                    ##求右下角 判斷依據為: 左上、上、左 取最小值+1
                    dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1
                    res=max(res,dp[i][j])
        return res**2
if __name__=='__main__':
    result=Solution()
    matrix = [["1","0","1","0","0"],
            ["1","0","1","1","1"],
            ["1","1","1","1","1"],
            ["1","0","0","1","0"]]
    ans=result.maximalSquare(matrix)
    print(ans)

## C++:

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        int res=0;
        //initial
        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;
            }
        }
        //dp
        for (int i=1; i<m; i++){
            for (int j=1; j<n; j++){
                if (matrix[i][j]=='1'){
                    dp[i][j]=min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1])+1;
                    res=max(res,dp[i][j]);
                }
            }
        }
        return res*res;
    }
};