Skip to content

221 maximal square

221. Maximal Square

题目: https://leetcode.com/problems/maximal-square/

难度: Medium

tag: DP

递推公式,一开始想的很简单:

dp[i][j] = dp[i-1][j-1] + 1 #如果dp[i-1][j-1]为1,dp[i-1][j]为1,dp[i][j-1]为1

很明显的错误,一旦遇到更大的方块就会有问题

然后看了hint,其实递推方程式是很有技巧的,左上角,左边,上面,相邻的三个部分最小的+1,当然,前提也是要这里dp[i][j] 为1,然后我们再会去看其他的部分。

看个例子

原本的matrix                     DP

1 0 1 0 0                     1 0 1 0 0
1 0 1 1 1            →        1 0 1 1 1 
1 1 1 1 1                     1 1 1 2 2
1 0 0 1 0                     1 0 0 1 0

是非常make sense的,因为最小的必定包括了周边的1,然后再加1,否则如果是0的话那么就为0.

而naïve的错误的递推公式是因为一个square考虑的部分是k * k的部分, k * k 部分都必定为1.

而正确的递推公式

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

则完美的考虑了这一情况

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        dp = []
        for i in matrix:
            tmp = []
            for j in i:
                tmp.append(int(j))
            dp.append(tmp)

        row = len(dp)
        col = len(dp[0]) if row else 0


        for i in range(1,row):
            for j in range(1,col):
                if dp[i][j] == 1:
                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) + 1


        maxv = 0
        for i in range(row):
            for j in range(col):
                if dp[i][j] > maxv:
                    maxv = dp[i][j]
        return maxv * maxv


回到顶部