LeetCode 1277. 统计全为 1 的正方形子矩阵【动态规划】1613

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释：
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.
1
2
3
4
5
6
7
8
9
10
11
12

示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.
1
2
3
4
5
6
7
8
9
10
11

提示：

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

---

解法 动态规划/递推（最优）

本题和 221. 最大正方形 非常类似，使用的方法也几乎相同。

我们用 $dp[i][j]$ 表示以 $(i,j)$ 为右下角的正方形的最大边长，那么除此定义之外，$dp[i][j]=x$ 也表示以 $(i,j)$ 为右下角的正方形的数目为 $x$（即边长为 $1,2,...,x$ 的正方形各一个）。在计算出所有的 $dp[i][j]$ 后，我们将它们进行累加，就可以得到矩阵中正方形的数目。

我们尝试挖掘 $dp[i][j]$ 与相邻位置的关系来计算出 $dp[i][j]$ 的值。

如上图所示，若对于位置 $(i,j)$ 有 $dp[i][j]=4$ ，我们将以 $(i,j)$ 为右下角、边长为 $4$ 的正方形涂上色，可以发现其左侧位置 $(i,j-1)$ ，上方位置 $(i-1,j)$ 和左上位置 $(i-1,j-1)$ 均可以作为一个边长为 $4-1=3$ 的正方形的右下角。也就是说，这些位置的的 $dp$ 值至少为 $3$ ，即：

dp[i][j - 1] >= dp[i][j] - 1
dp[i - 1][j] >= dp[i][j] - 1
dp[i - 1][j - 1] >= dp[i][j] - 1
1
2
3

将这三个不等式联立，可以得到：
$$\min (dp[i][j-1],dp[i-1][j],dp[i-1][j-1])\ge dp[i][j]-1$$

这是我们通过固定 $dp[i][j]$ 的值，判断其相邻位置与之的关系得到的不等式。同理，我们也可以固定 $dp[i][j]$ 相邻位置的值，得到另外的限制条件。

如上图所示，假设 $dp[i][j-1]$ ，$dp[i-1][j]$ 和 $dp[i-1][j-1]$ 中的最小值为 $3$ ，也就是说，$(i,j-1)$ ，$(i-1,j)$ 和 $(i-1,j-1)$ 均可以作为一个边长为 $3$ 的正方形的右下角。我们将这些边长为 $3$ 的正方形依次涂上色，可以发现，如果位置 $(i,j)$ 的元素为 $1$ ，那么它可以作为一个边长为 $4$ 的正方形的右下角，$dp$ 值至少为 $4$ ，即：
$$dp[i][j]\ge \min (f[i][j-1],f[i-1][j],f[i-1][j-1])+1$$
将其与上一个不等式联立，可以得到：
$$dp[i][j]=\min (dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1$$
这样我们就得到了 $dp[i][j]$ 的递推式。此外还要考虑边界（$i=0$ 或 $j=0$）以及位置 $(i,j)$ 的元素为 $0$ 的情况。

我们按照行优先的顺序依次计算 $dp[i][j]$ 的值，就可以得到最终的答案。

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 1) {
                    dp[i + 1][j + 1] = 1 + 
                        min(dp[i][j], 
                            min(dp[i][j + 1], dp[i + 1][j]));
                    ans += dp[i + 1][j + 1];
                }
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

由于递推式中 $dp[i][j]$ 只与本行和上一行的若干个值有关，因此空间复杂度可以优化至 $O(N)$ 。

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> dp(n + 1);
        int ans = 0;
        int pre = 0, temp = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 1) {
                    temp = dp[j + 1];
                    dp[j + 1] = 1 + 
                        min(pre, 
                            min(dp[j + 1], dp[j]));
                    pre = temp; // pre为dp[i][j]
                    ans += dp[j + 1];
                } else pre = dp[j + 1], dp[j + 1] = 0; // 注意此时也要记录dp[i][j],并更新dp[i+1][j+1]
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析：

• 时间复杂度：$O(mn)$
• 空间复杂度：$O(n)$