题目地址：

https://leetcode.com/problems/count-square-submatrices-with-all-ones/

给定一个 m × n m\times n m×n的 0 − 1 0-1 0−1矩阵 A A A，问其有多少个 1 1 1方阵。

如果能求出 f [ i ] [ j ] f[i][j] f[i][j]， f [ i ] [ j ] f[i][j] f[i][j]是以 A [ i ] [ j ] A[i][j] A[i][j]为右下角的最大的 1 1 1方阵的边长（这个边长也等于以 A [ i ] [ j ] A[i][j] A[i][j]为右下角的 1 1 1方阵有多少个），那么很显然 ∑ f \sum f ∑f就是答案。考虑如何递推 f f f。首先如果 A [ i ] [ j ] = 0 A[i][j]=0 A[i][j]=0则 f [ i ] [ j ] = 0 f[i][j]=0 f[i][j]=0；否则的话看一下 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]和 f [ i ] [ j − 1 ] f[i][j-1] f[i][j−1]，如果 f [ i − 1 ] [ j ] = f [ i ] [ j − 1 ] = x f[i-1][j]=f[i][j-1]=x f[i−1][j]=f[i][j−1]=x，那么看一下 A [ i − x ] [ j − x ] A[i-x][j-x] A[i−x][j−x]，如果其为 1 1 1，则 f [ i ] [ j ] = 1 + x f[i][j]=1+x f[i][j]=1+x，否则 f [ i ] [ j ] = x f[i][j]=x f[i][j]=x；如果 f [ i − 1 ] [ j ] ≠ f [ i ] [ j − 1 ] f[i-1][j]\ne f[i][j-1] f[i−1][j]​=f[i][j−1]，那么 f [ i ] [ j ] = 1 + min ⁡ { f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] } f[i][j]=1+\min\{f[i-1][j],f[i][j-1]\} f[i][j]=1+min{f[i−1][j],f[i][j−1]}。代码如下：

public class Solution {
    public int countSquares(int[][] mat) {
        for (int i = 1; i < mat.length; i++) {
            for (int j = 1; j < mat[0].length; j++) {
                if (mat[i][j] == 0) {
                    continue;
                }
                
                int up = mat[i - 1][j], left = mat[i][j - 1];
                if (up != left) {
                    mat[i][j] = 1 + Math.min(up, left);
                } else {
                    mat[i][j] = up + (mat[i - up][j - left] != 0 ? 1 : 0);
                }
            }
        }
    
        int res = 0;
        for (int[] row : mat) {
            for (int x : row) {
                res += x;
            }
        }
        
        return res;
    }
}

时间复杂度 O ( m n ) O(mn) O(mn)，空间 O ( 1 ) O(1) O(1)。