# 1277. Count Square Submatrices with All Ones
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/count-square-submatrices-with-all-ones/description/
## 思路
和[0221. Maximal Square](https://hackmd.io/0Ie3z7ZRSH6sB5fMh1ZP7g)本质上是一样的
本质就是求01矩阵里面，以(i,j)为右下角的正方形最大边长是多少。边长多大，就意味着以(i,j)为右下角的正方形能有多少个
解这道题的状态转移方程为```dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])+1```
## Code

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int sum = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j]==0) continue;
                if(i!=0 && j!=0){
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1;
                }
                else dp[i][j]=1;
                sum += dp[i][j];
            }
        }
        return sum;
    }
}