1 題目描述


給定一個二維矩陣matrix，找到只包含1的最大正方形，並返回其面積。

2 解法

其實看到這種2D的DP題目，老樣子可以先把圖片畫出來，然後開始找規律，我們可以先定義如下：
dp[i][j] 代表以matrix[i][j]為右下角的最大正方形邊長，這樣的話我們就可以推導出以下公式：

  • 如果matrix[i][j] == 1
    • 那麼dp[i][j]就是min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，這裡的+1是因為matrix[i][j]是1，所以可以構成一個正方形
  • 如果matrix[i][j] == 0
    • 那麼dp[i][j]就是0，因為無法構成正方形

比較特別的是思考的方式：但是必須考慮dp[i][j]的時候，周遭的cell必須都是計算過的，才可以透過解決小問題來解決大問題

  1. 可以從最左下角開始思考，那我們就要看dp[i][j]的左邊、下面、下斜角的cell
  2. 或是從最右上角開始思考，但是必須考慮dp[i][j]的右邊、上面、上斜角的cell

Solution1: 左下角開始

Solution2: 右上角開始

2.1 Recursion + Memoization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
Time: O(m*n)
Space: O(m*n)
"""
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        rows, columns = len(matrix), len(matrix[0])
        dp = {}
        def helper(r: int, c: int):
            if r >= rows or c >= columns:
                return 0
            if matrix[r][c] == '0':
                return 0
            if (r, c) in dp:
                return dp[(r, c)]
            down = helper(r+1, c)
            right = helper(r, c+1)
            down_right = helper(r+1, c+1)
            dp[(r, c)] = min(down, right, down_right) + 1
            return dp[(r, c)]
        
        helper(0, 0)
        return max(dp.values()) ** 2

2.1 Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
"""
Time: O(m*n)
Space: O(m*n)
"""
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        rows, columns = len(matrix), len(matrix[0])
        dp = [[0 for _ in range(columns)] for _ in range(rows)]
        max_side = 0
        for i in range(rows):
            for j in range(columns):
                if matrix[i][j] == "1":
                    dp[i][j] = 1
                    if i > 0 and j > 0:
                        dp[i][j] = 1 + min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])
                    if dp[i][j] > biggest:
                        biggest = dp[i][j]

        return biggest ** 2
```   

## 2.2 Iterative with Space Optimization
```python
"""
Time: O(m*n)
Space: O(n)
"""
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        rows, columns = len(matrix), len(matrix[0])
        dp = [[0 for _ in range(columns)] for _ in range(2)]
        max_side = 0
        for i in range(rows):
            for j in range(columns):
                # 只有cell是1的時候才需要計算
                if matrix[i][j] == "1":
                    dp[1][j] = 1
                    # 不是邊緣的狀況
                    if i > 0 and j > 0:
                        dp[1][j] = 1 + min(dp[0][j], dp[0][j-1], dp[1][j-1])
                    # 更新最大邊長
                    if dp[1][j] > biggest:
                        biggest = dp[1][j]
            # 更新dp把new row更新到old row
            dp[0] = dp[1]
            # 初始化動作才不會因為記憶體指向導致出錯
            dp[1] = [0] * columns

        return biggest ** 2

3 總結

這題不難，但是我沒想到dp儲存的竟然是邊長，而不是面積，這點要注意一下。這題的解法也是比較直觀，就是從左下角或是右上角開始思考，然後找出規律，這樣就可以寫出解法了。但是最需要注意的是，當我們使用iterative並且挑選要從左下角或是右上角開始時，要記得選擇周邊的cell必須是已經計算過的，這樣才能透過小問題解決大問題。