f[i][j] = x 也表示以 (i, j) 为右下角的正方形的数目为 x（即边长为 1, 2, ..., x 的正方形各一个）

依然是使用动态规划的做法，计算出所有的 f[i][j] ，累加得到最终的答案

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));
        int res = 0;
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (i == 0 || j == 0) {
                    f[i][j] = matrix[i][j];
                } else if (matrix[i][j] == 0) {
                    f[i][j] = 0;
                } else {
                    f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j],f[i][j - 1])) + 1;
                }
                res += f[i][j];
            }
        }
        return res;
    }
};

寻找递推关系式

1、

f[i][j] 是一个边长为4的正方形上色。然后发现其左、右、左上位置均可以作为一个边长为 4 - 1 的正方形的右下角。也就是说，这些位置的 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

$f[i][j] \geq \min (f[i][j-1], f[i-1][j], f[i-1][j-1])+1$

2、

上面时固定了 f[i][j] 的值，这里是固定周围 f

$f[i][j] \leq \min (f[i][j-1], f[i-1][j], f[i-1][j-1])+1$

将两个式子联立后，（一个 leq 一个 geq）得到 相等

$f[i][j] = \min (f[i][j-1], f[i-1][j], f[i-1][j-1])+1$