🔗 🟡 1277. Count Square Submatrices with All Ones 1613

tags: Weekly Contest 165 陣列(Array) 矩陣(Matrix) 動態規劃(Dynamic Programming)

題意

給定一個大小為 m×nm \times n 的矩陣，其中只包含 11 和 00，返回有多少個 正方形 子矩陣的所有元素都是 11。

思路：動態規劃(Dynamic Programming)

由於 Bottom-Up DP 的遍歷方向和 Top-Down DP 的考慮方向相反，因此在寫 Top-Down DP 時，最好是能夠從後往前思考，這樣轉換為 Bottom-Up DP 的時候，能夠直接從前往後遍歷，會比較方便。

方法一：Top-Down DP: 記憶化搜尋(Memoization)

首先令 f(i,j)f(i, j) 為以 (i,j)(i, j) 為右下角的最大正方形邊長，則有以下性質：

  1. 對於任何一個正方形，其右下角的座標可以唯一確定這個正方形
  2. 如果該位置是 0，則不可能形成任何正方形
  3. 如果該位置是 1，則可能形成的正方形大小取決於其左方、上方、左上方的情況，當前位置的正方形邊長為其左方、上方、左上方的正方形邊長最小值 +1+1

關於上述的第 3 點可以反過來思考，如果以 (i,j)(i, j) 為右下角的最大正方形邊長為 kk，則以 (i−1,j)(i-1, j)、(i,j−1)(i, j-1)、(i−1,j−1)(i-1, j-1) 為右下角的正方形邊長至少為 k−1k - 1。

因此，我們可以得到以下轉移方程：

f(i,j)={0if matrix[i][j]=01+min⁡(f(i−1,j),f(i,j−1),f(i−1,j−1))if matrix[i][j]=1f(i, j) = \begin{cases} 0 & \text{if } matrix[i][j] = 0 \\ 1 + \min(f(i-1, j), f(i, j-1), f(i-1, j-1)) & \text{if } matrix[i][j] = 1 \end{cases}

因此，我們可以從矩陣的左上角開始，逐步計算每個位置的 f(i,j)f(i, j)，最後將所有 f(i,j)f(i, j) 的值相加，即為答案。

由於過程中存在許多重複的子問題，因此我們可以使用 自頂向下(Top-Down) 的 記憶化搜尋(Memoization) 來避免重複計算相同的子問題。

複雜度分析

  • 時間複雜度：O(m×n)\mathcal{O}(m \times n)，狀態數量為 m×nm \times n，計算轉移的時間複雜度為 O(1)O(1)
  • 空間複雜度：O(m×n)\mathcal{O}(m \times n)，同狀態數量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        @cache
        def dfs(i, j): # 以 (i, j) 為右下角的最大正方形邊長
            if i < 0 or j < 0:
                return 0
            if matrix[i][j] == 0:
                return 0
            return 1 + min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1))
        ans = 0
        for i in range(m):
            for j in range(n):
                ans += dfs(i, j)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> memo(m, vector<int>(n, -1));
        auto dfs = [&](auto&& dfs, int i, int j) -> int {
            if (i < 0 || j < 0) return 0;
            int& res = memo[i][j];
            if (res != -1) return res;
            if (matrix[i][j] == 0) return res = 0;
            return res = 1 + min({dfs(dfs, i - 1, j), dfs(dfs, i, j - 1), dfs(dfs, i - 1, j - 1)});
        };
        int ans = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                ans += dfs(dfs, i, j);
        return ans;
    }
};

方法二：Bottom-Up DP

同樣地，我們也可以使用 自底向上(Bottom-Up) 的 動態規劃(Dynamic Programming) 來避免重複計算相同的子問題。

由於我們在方法一中是從後往前思考，因此轉換為 Bottom-Up DP 的時候，需要從前往後遍歷。轉移方程相同，但需要修改邊界情況，當 ii 或 jj 為 00 時，若 matrix[i][j]=1matrix[i][j] = 1，則最大正方形邊長為 11；否則為 00。

複雜度分析

  • 時間複雜度：O(m×n)\mathcal{O}(m \times n)，狀態數量為 m×nm \times n，計算轉移的時間複雜度為 O(1)O(1)
  • 空間複雜度：O(m×n)\mathcal{O}(m \times n)，同狀態數量。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        f = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    continue
                if i == 0 or j == 0:
                    f[i][j] = 1
                else:
                    f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1
        return sum(sum(row) for row in f)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> f(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) continue;
                if (i == 0 || j == 0) {
                    f[i][j] = 1;
                } else {
                    f[i][j] = min({f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]}) + 1;
                }
            }
        }
        int ans = 0;
        for (const auto& row : f)
            ans += accumulate(row.begin(), row.end(), 0);
        return ans;
    }
};

寫在最後

PROMPT

Mystical Moonlight Encounter: A young anime girl, dressed in a black cape and witch hat, holds a pumpkin with an intense gaze. Standing before a large window framing a moonlit night sky, her focus is riveted on the pumpkin. To her left, a vibrant yellow pumpkin sits atop a straw bale amidst autumn leaves, adding a burst of warmth to the enchanting scene.