> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/zou-ge/maximal-square.md).

# 221. Maximal Square

https\://leetcode.com/problems/maximal-square/description/

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

**Example:**

```
Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4
```

## Thoughts

01矩阵返回内部由1组成的最大方阵的大小。argmax + 格子 => DP。dp\[i]\[j]表示在(i, j)处最大方阵边长是多少，当它是1时，它由左，上和斜能构成的最大方阵拼接而成，且大小受制于邻居中最小的。总结果是argmax\_(i, j)，所有子结果中最优的。

## Code

```python
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        M, N = len(matrix), len(matrix[0]) if len(matrix) > 0 else 0
        dp = [[0] * (N + 1) for i in range(M + 1)]
        res = 0
        for i in range(1, M + 1):
            for j in range(1, N + 1):
                if matrix[i - 1][j - 1] == '0':
                    continue
                dp[i][j] = min(min(dp[i - 1][j], dp[i - 1][j - 1]), dp[i][j - 1]) + 1
                res = max(res, dp[i][j])
        return res ** 2
        
```

## Analysis

Errors:

1. m == 0 || matrix\[0] == null没考虑
2. return pow(2, max)

时间复杂度O(mn).