# Maximum Square

DP

以当前position (i,j) 作为点, dp\[i]\[j] 代表以i，j为顶点最大的正方形长度

recurrence relation 

$$
dp\[i]\[j] = min(dp\[i-1]\[j-1], dp\[i]\[j-1], dp\[i-1]\[j]) + 1,
when,  matrix\[i]\[j] = 1
$$

```python
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        length = 0
        m = len(matrix)
        if m == 0:
            return 0
        n = len(matrix[0])
        dp = [n*[0] for _ in range(m)]
        for i in range(m):
            if matrix[i][0] == "1":
                dp[i][0] = 1
                length =1
        for j in range(n):
            if matrix[0][j] == "1":
                dp[0][j] = 1
                length =1
        for i in range(1,m):
            for j in range(1,n):
                if matrix[i][j] == "1":
                    dp[i][j] = min([dp[i][j-1],dp[i-1][j],dp[i-1][j-1]])+1
                    length = max(length,dp[i][j])
        return length**2
```

把上面的code简化一下成为

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