动态规划

主要思想

创建一个二维 dp 数组，接着遍历矩阵，然后在 dp 里面存储当前遍历到的最大的正方形的边长，最后取出 dp 的最大值，平方即面积。

状态转移方程

讨论区第一个那个图 其实已经很明了了，但我这里还是提一嘴。
0 自然没什么问题；至于 min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1，其中的 1 指的是当前块，min 大家想一下就知道了，类似于 短板效应，最大的 囊括当前块 的正方形当然取决于最短的那条边。

ps: 几个小技巧

• 巧用 map 取二维数组最值
• 一般而言 * 快于 power 快于 **

#
# 最大正方形
# @param matrix char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , matrix ):
        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == '0':
                    dp[i][j] = 0
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
        res = max(map(max, dp))
        return res * res