> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/niu-ke-0108-zhong-deng-zui-da-zheng-fang-xing.md).

# 最大正方形

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#中等) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#动态规划)

> [最大正方形\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/0058c4092cec44c2975e38223f10470e)

**问题简述**

```
给定一个由'0'和'1'组成的2维矩阵，返回该矩阵中最大的由'1'组成的正方形的面积，输入的矩阵是字符形式而非数字形式。
```

**思路：动态规划**

* 定义 `dp(i, j) := 以坐标(i,j)为右下角的最大正方形边长`
* 则 `dp(i, j) = min( dp(i-1,j), dp(i,j-1), dp(i-1,j-1) ) + 1`，当 `matrix[i-1][j-1] == 1` 时；

<details>

<summary><strong>Python 写法1：递归</strong></summary>

```python
class Solution:
    def solve(self , matrix: List[List[str]]) -> int:
        if not matrix: return 0
        
        self.mx = 0
        
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def dp(i, j):  # 以坐标(i,j)为右下角的最大正方形边长
            if i == 0 or j == 0: return 0
            r1, r2, r3 = dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)
            if matrix[i - 1][j - 1] == '1':
                ret = min(r1, r2, r3) + 1
                self.mx = max(self.mx, ret)
                return ret
            return 0
        
        m, n = len(matrix), len(matrix[0]) 
        dp(m, n)
        return self.mx ** 2
```

</details>

<details>

<summary><strong>Python 写法2：迭代</strong></summary>

```python
class Solution:
    def solve(self , matrix: List[List[str]]) -> int:
        if not matrix: return 0
        
        self.mx = 0
        m, n = len(matrix), len(matrix[0]) 
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                r1, r2, r3 = dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]
                if matrix[i - 1][j - 1] == '1':
                    ret = min(r1, r2, r3) + 1
                    self.mx = max(self.mx, ret)
                    dp[i][j] = ret
        
        return self.mx ** 2
```

</details>