Code & Func

第50天。

恍恍惚惚，就50天了。

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

Return 4.

让人很意外，这是一道动态规划的题目。

先说说我的非动态规划的解法：

大概的想法是，做一次遍历，每次遇到1,就向下拓展，如果扩展，扩展的方法是就是只需要看当前正方形的外围是否都是1，如果都是1,那么我们就可以继续向下扩展，这样就可以遍历出一个正方形，然后我们在对matrix进行遍历的时候还可以通过当前的最大面积来提早结束遍历：

1
def expend(self,matrix,i,j,ret):
2
    """
3
    :type matrix: List[List[str]]
4
    :type i: int
5
    :type j: int
6
    :type ret: int
7
    :rtype ret
8
    """
9
    if i >= len(matrix) or j >= len(matrix[0]):
10
        return ret
11
    for k in range(ret+1):
12
        if matrix[i][j - k] == '0' or matrix[i-k][j] == '0':
13
            return ret
14
    return self.expend(matrix,i+1,j+1,ret+1)
15

14 collapsed lines
16
def maximalSquare1(self, matrix):
17
    """
18
    :type matrix: List[List[str]]
19
    :rtype: int
20
    """
21
    ret,i = 0,0
22
    while i + ret < len(matrix):
23
        j = 0
24
        while j + ret < len(matrix[0]):
25
            if matrix[i][j] == '1':
26
                ret = max(ret,self.expend(matrix,i+1,j+1,1))
27
            j += 1
28
        i += 1
29
    return ret*ret

挺暴力的方法，不知道是不是因为可以提前结束，所以这个方法也直接AC了。

然后是DP的解法。

在解决这个问题之前，我们先考虑如果求出以matrix[i][j]为右下角的正方形最大面积。

如果matrix[i][j] = '0',那么显然size[i][j] = 0 如果matrix[i][j] = '1',那么我们需要考虑其向上，向左，向左上的最大面积。

假设size[i-1][j-1] = 2,则我们至少可以知道：

1
[
2
    [1,1,*]
3
    [1,1,*]
4
    [*,*,-]
5
]

如果size[i][j-1] = 2,我们至少知道：

1
[
2
    [*,*,*]
3
    [1,1,*]
4
    [1,1,-]
5
]

如果size[i-1][j] = 2,我们至少知道：

1
[
2
    [*,1,1]
3
    [*,1,1]
4
    [*,*,-]
5
]

从上面可以看出来，只有当size[i-1][j-1] == 2 and size[i][j-1] == 2 and size[i-1][j-1] == 2时，size[i][j] == 3,

则我们可以得出以下递推式：

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

然后我们还需要考虑一下边界条件，因为当i=0或j=0时，上面的递推式是没有考虑到的，我们再加上：

size[i][j] = (matrix[i][j] == '1') where i == 0 or j == 0

然后我们就可以写出以下解法：

1
def maximalSquare(self,matrix):
2
    if len(matrix) == 0:
3
        return 0
4
    dp1 = []
5
    ret = 0
6
    for i in range(len(matrix[0])):
7
        t = int(matrix[0][i] == '1')
8
        dp1.append(t)
9
        ret = max(ret,t)
10
    for i in range(1,len(matrix)):
11
        dp2 = [ 0 for i in range(len(matrix[0])) ]
12
        dp2[0] = int(matrix[i][0] == '1')
13
        ret = max(dp2[0],ret)
14
        for j in range(1,len(matrix[0])):
15
            if matrix[i][j] == '1':
4 collapsed lines
16
                dp2[j] = min(min(dp1[j-1],dp1[j]),dp2[j-1]) + 1
17
            ret = max(ret,dp2[j])
18
        dp1 = dp2
19
    return ret*ret