# 0221. Maximal Square
###### tags: `Leetcode` `Medium` `Dynamic Programming`
## 思路
和[1277. Count Square Submatrices with All Ones](https://hackmd.io/rfyE5TsLSGmlkOMPANdsGQ)本质上是一样的
本质就是求01矩阵里面，以(i,j)为右下角的正方形最大边长是多少
有了最大的边长 就有了最大的square
解这道题的状态转移方程为```dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])+1```
## Code

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        ans = 0
        m, n = len(matrix), len(matrix[0])
        dp = [[0 for _ in range(n)] for i in range(m)]
        for i in range(m):
            for j in range(n):
                if matrix[i][j]=='0':
                    continue
                if i>0 and j>0:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
                else:
                    dp[i][j] = 1
                ans = max(ans, dp[i][j]*dp[i][j])
        return ans

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        int ans = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j]=='0') continue;
                if(i!=0 && j!=0) dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1;
                else dp[i][j] = 1;
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans*ans;
    }
}