题目地址：

https://www.lintcode.com/problem/count-square-submatrices-with-all-ones/description

给定一个$0-1$矩阵$A$，问其有多少个值全为$1$的方阵。

思路是动态规划。设$f[i][j]$是以$A[i][j]$为右下角的$1$方阵的最大边长。当$A[i][j]=0$时，$f[i][j]=1$；否则看一下$f[i-1][j]$和$f[i][j-1]$，如果$f[i-1][j]\ne f[i][j-1]$，那么$f[i][j]=1+\min \{f[i-1][j],f[i][j-1]\}$，如果$f[i-1][j]=f[i][j-1]=x$，那么$f[i][j]=\min \{1+x,1+f[i-1][j-1]\}$。那么以$A[i][j]$为右下角的$1$方阵的数量就是$f[i][j]$，所以最终答案就是将$f$矩阵里的数字全加起来即可。代码如下：

public class Solution { /** * @param matrix: a matrix * @return: return how many square submatrices have all ones */ public int countSquares(int[][] matrix) { // write your code here int m = matrix.length, n = matrix[0].length; int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { dp[i][j] = 0; } else { dp[i][j] = 1; int left = 0, up = 0; if (i > 0) { left = dp[i - 1][j]; } if (j > 0) { up = dp[i][j - 1]; } if (left != up) { dp[i][j] = 1 + Math.min(left, up); } else if (i > 0 && j > 0) { dp[i][j] = Math.min(1 + left, 1 + dp[i - 1][j - 1]); } } } } int res = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { res += dp[i][j]; } } return res; } }

时空复杂度$O(mn)$。