手撕代码：0-1矩阵的最大正方形

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

	def maximalSquare(matrix):



	    for i, r in enumerate(matrix):
        r = matrix[i] = list(map(int, r))
        for j, c in enumerate(r):
            if i * j * c:
                r[j] = min(matrix[i - 1][j], r[j - 1], matrix[i - 1][j - 1]) + 1



	    return max(map(max, matrix + [[0]])) ** 2 # in case of the matrix is [], we add the [[0]]

(动态规划)
其实这道题可以是一个动态规划问题，用dp[i][j]记录到达(i, j)位置所能组成的最大正方形的边长。

我们首先来考虑边界情况，也就是当i或j为0的情况，那么在首行或者首列中，必定有一个方向长度为1，那么就无法组成长度超过1的正方形，最多能组成长度为1的正方形，条件是当前位置为1。

而对于递推公式，对于任意一点dp[i][j]，由于该点是正方形的右下角，所以该点的右边，下边，右下边都不用考虑，关心的就是左边，上边，和左上边，只有当前(i, j)位置为1，dp[i][j]才有可能大于0，否则dp[i][j]一定为0。当(i, j)位置为1，此时要看dp[i-1][j-1], dp[i][j-1]，和dp[i-1][j]这三个位置，我们找其中最小的值，并加上1，就是dp[i][j]的当前值了，这个并不难想，毕竟不能有0存在，所以只能取交集，最后再用dp[i][j]的值来更新结果res的值即可。

时间复杂度分析：

int maximalSquare(vector<vector<char>>& matrix) {
    int m=matrix.size();
    int n=matrix[0].size();
    vector<vector<int>> dp(m,vector<int>(n,0));
    for(int i=0;i<m;i++){
        dp[i][0]=matrix[i][0];
        dp[i][n-1]=matrix[i][n-1];
    }
    for(int j=0;j<n;j++){
        dp[0][j]=matrix[0][j];
        dp[m-1][j]=matrix[m-1][j];
    }
    int res=0;
    for(int i=1;i<m;i++)
        for(int j=1;j<n;j++){
            if(matrix[i][j]=='0')
                dp[i][j]=0;
            else{
                dp[i][j]=1;
                dp[i][j]+=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))
                res=max(res,dp[i][j]);
            }
        }
    return res*res;
}