给你一个 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.
示例 2：
输入：matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.
提示：
1 <= arr.length <= 3001 <= arr[0].length <= 3000 <= arr[i][j] <= 1
解法 动态规划/递推（最优）
本题和 221. 最大正方形 非常类似，使用的方法也几乎相同。
我们用 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示以 ( i , j ) (i,j) (i,j) 为右下角的正方形的最大边长，那么除此定义之外， d p [ i ] [ j ] = x dp[i][j] = x dp[i][j]=x 也表示以 ( i , j ) (i,j) (i,j) 为右下角的正方形的数目为 x x x（即边长为 1 , 2 , . . . , x 1, 2, ..., x 1,2,...,x 的正方形各一个）。在计算出所有的 d p [ i ] [ j ] dp[i][j] dp[i][j] 后，我们将它们进行累加，就可以得到矩阵中正方形的数目。
我们尝试挖掘 d p [ i ] [ j ] dp[i][j] dp[i][j] 与相邻位置的关系来计算出 d p [ i ] [ j ] dp[i][j] dp[i][j] 的值。
如上图所示，若对于位置 ( i , j ) (i,j) (i,j) 有 d p [ i ] [ j ] = 4 dp[i][j] = 4 dp[i][j]=4 ，我们将以 ( i , j ) (i,j) (i,j) 为右下角、边长为 4 4 4 的正方形涂上色，可以发现其左侧位置 ( i , j − 1 ) (i, j - 1) (i,j−1) ，上方位置 ( i − 1 , j ) (i - 1, j) (i−1,j) 和左上位置 ( i − 1 , j − 1 ) (i - 1, j - 1) (i−1,j−1) 均可以作为一个边长为 4 − 1 = 3 4 - 1 = 3 4−1=3 的正方形的右下角。也就是说，这些位置的的 d p dp dp 值至少为 3 3 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
将这三个不等式联立，可以得到：
min ( d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − 1 ] ) ≥ d p [ i ] [ j ] − 1 \min\big(dp[i][j - 1],\ dp[i - 1][j],\ dp[i - 1][j - 1]\big) \geq dp[i][j] - 1 min(dp[i][j−1], dp[i−1][j], dp[i−1][j−1])≥dp[i][j]−1
这是我们通过固定 d p [ i ] [ j ] dp[i][j] dp[i][j] 的值，判断其相邻位置与之的关系得到的不等式。同理，我们也可以固定 d p [ i ] [ j ] dp[i][j] dp[i][j] 相邻位置的值，得到另外的限制条件。
如上图所示，假设 d p [ i ] [ j − 1 ] dp[i][j - 1] dp[i][j−1] ， d p [ i − 1 ] [ j ] dp[i - 1][j] dp[i−1][j] 和 d p [ i − 1 ] [ j − 1 ] dp[i - 1][j - 1] dp[i−1][j−1] 中的最小值为 3 3 3 ，也就是说， ( i , j − 1 ) (i, j - 1) (i,j−1) ， ( i − 1 , j ) (i - 1, j) (i−1,j) 和 ( i − 1 , j − 1 ) (i - 1, j - 1) (i−1,j−1) 均可以作为一个边长为 3 3 3 的正方形的右下角。我们将这些边长为 3 3 3 的正方形依次涂上色，可以发现，如果位置 ( i , j ) (i,j) (i,j) 的元素为 1 1 1 ，那么它可以作为一个边长为 4 4 4 的正方形的右下角， d p dp dp 值至少为 4 4 4 ，即：
d p [ i ] [ j ] ≥ min ( f [ i ] [ j − 1 ] , f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − 1 ] ) + 1 dp[i][j] \geq \min\big(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]\big) + 1 dp[i][j]≥min(f[i][j−1],f[i−1][j],f[i−1][j−1])+1
将其与上一个不等式联立，可以得到：
d p [ i ] [ j ] = min ( d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − 1 ] ) + 1 dp[i][j] = \min\big(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]\big) + 1 dp[i][j]=min(dp[i][j−1],dp[i−1][j],dp[i−1][j−1])+1
这样我们就得到了 d p [ i ] [ j ] dp[i][j] dp[i][j] 的递推式。此外还要考虑边界（ i = 0 i = 0 i=0 或 j = 0 j = 0 j=0）以及位置 ( i , j ) (i,j) (i,j) 的元素为 0 0 0 的情况。
我们按照行优先的顺序依次计算 d p [ i ] [ j ] dp[i][j] 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;
}
};
由于递推式中 d p [ i ] [ j ] dp[i][j] dp[i][j] 只与本行和上一行的若干个值有关，因此空间复杂度可以优化至 O ( N ) O(N) 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;
}
};
复杂度分析：
- 时间复杂度： O ( m n ) O(mn) O(mn)
- 空间复杂度： O ( n ) O(n) O(n)