本题和 221. 最大正方形 非常类似，使用的方法也几乎相同。
我们用 f[i][j] 表示以 (i, j) 为右下角的正方形的最大边长，那么除此定义之外，f[i][j] = x 也表示以 (i, j) 为右下角的正方形的数目为 x（即边长为 1, 2, ..., x 的正方形各一个）。在计算出所有的 f[i][j] 后，我们将它们进行累加，就可以得到矩阵中正方形的数目。
我们尝试挖掘 f[i][j] 与相邻位置的关系来计算出 f[i][j] 的值。
如上图所示，若对于位置 (i, j) 有 f[i][j] = 4，我们将以 (i, j) 为右下角、边长为 4 的正方形涂上色，可以发现其左侧位置 (i, j - 1)，上方位置 (i - 1, j) 和左上位置 (i - 1, j - 1) 均可以作为一个边长为 4 - 1 = 3 的正方形的右下角。也就是说，这些位置的的 f 值至少为 3，即：
\[f[i][j - 1] >= f[i][j] - 1
\f[i - 1][j] >= f[i][j] - 1
\f[i - 1][j - 1] >= f[i][j] - 1
\]
将这三个不等式联立，可以得到：
\[\min\big(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]\big) \geq f[i][j] - 1
\]
这是我们通过固定 f[i][j] 的值，判断其相邻位置与之的关系得到的不等式。同理，我们也可以固定 f[i][j] 相邻位置的值，得到另外的限制条件。
如上图所示，假设 f[i][j - 1]，f[i - 1][j] 和 f[i - 1][j - 1] 中的最小值为 3，也就是说，(i, j - 1)，(i - 1, j) 和 (i - 1, j - 1) 均可以作为一个边长为 3 的正方形的右下角。我们将这些边长为 3 的正方形依次涂上色，可以发现，如果位置 (i, j) 的元素为 1，那么它可以作为一个边长为 4 的正方形的右下角，f 值至少为 4，即：
\[f[i][j]≥min(f[i][j?1],f[i?1][j],f[i?1][j?1])+1
\]
将其与上一个不等式联立，可以得到：
\[f[i][j] = \min\big(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]\big) + 1
\]
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> f(n + 1, vector<int>(m + 1));
int res = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(matrix[i - 1][j - 1] == 1)
{
f[i][j] = min(f[i - 1][j], min(f[i][j - 1], f[i - 1][j - 1])) + 1;
res += f[i][j];
}
return res;
}
};