[LeetCode]Maximal Square

我们用DP[i][j][k]来表示以matrix[i][j]为左上顶点的长度为k的区域是否是square，我们可以得到递推公式：

• DP[i][j][k] = true, if DP[i][j][k - 1], DP[i - 1][j][k - 1], DP[i][j - 1][k - 1], DP[i - 1][j - 1][k - 1]均为true
• 否则，DP[i][j][k] = false

假设输入matrix为m * n，时间复杂度O(m * n * min(m , n))，空间复杂度O(m * n * min(m , n))，代码如下：

但是很明显这个DP方程效率并不高，如果改变用DP[i][j] = k代表以matrix[i][j]作为右下顶点的square的最大长度为k，我们可以得到效率更高的DP方程，递推公式如下：

• if matrix[i][j] == '1' && DP[i - 1][j] > 0 && DP[i - 1][j - 1] > 0 && DP[i ][j - 1] > 0, DP[i][j] = min(DP[i - 1][j], DP[i - 1][j - 1], DP[i ][j - 1] )
• else if matrix[i][j] == '1', DP[i][j] = 1
• else DP[i][j] = 0

这个地推公式画个图很好理解，就不分析了。时间复杂度O(n * m)，空间复杂度O(m * n)，代码如下：

空间可以优化到O(n)，代码如下：