Maximal Square

这道题和求最大长方形那几道差不多，最重要的是要明确你的DP矩阵里面的值代表了什么，而这道题如果把dp[i][j]定为以坐标i,j为右下角顶点的正方形边长长度则此题就很好判断状态的递推了，状态方程

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 if matrix[i][j] == 1
dp[i][j] = 0 if matrix[i][j] == 0

下面是代码

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        n = len(matrix)
        if not n:
            return 0

        m = len(matrix[0])
        if not m:
            return 0

        dp = [[0] * m for _ in xrange(n)]
        result = 0
        for i in xrange(n):
            for j in xrange(m):
                if not i or not j:
                    dp[i][j] = int(matrix[i][j])
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1 if matrix[i][j] == '1' else 0
                result = max(result, dp[i][j])

        return result * result

此题空间优化只能优化到两排