Maximal Square

It's a typical dynamic programming problem. We just scan each row to see is there any new square or enlarging ones and refresh the maximum area. To better iterate, we store the length of square instead of area. When we visit a new position, we need to check its left element, its upper element and its upper-left element to decide whether there is a square meet the requisites. If the explanation is not clear, you can try to draw different situations to figure out how to check this.

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        dp, res = [[0] * len(matrix[0])], 0
        for i in range(len(matrix)):
            cur = []
            for j in xrange(len(matrix[0])):
                if matrix[i][j] == '1':
                    if not j:
                        value = 1
                    else:
                        value = min([dp[i][j-1], dp[i][j], cur[j-1]]) + 1
                    cur.append(value)
                    if value > res:
                        res = value
                else:
                    cur.append(0)
            dp.append(cur)
        return res * res