Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

&nbsp;
Example 1:

Input: matrix =
[
&nbsp; [0,1,1,1],
&nbsp; [1,1,1,1],
&nbsp; [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.


Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.


&nbsp;
Constraints:


	1 &lt;= arr.length&nbsp;&lt;= 300
	1 &lt;= arr[0].length&nbsp;&lt;= 300
	0 &lt;= arr[i][j] &lt;= 1


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:

        m = len(matrix)
        n = len(matrix[0])

        dp = [[0 for _ in range(n)] for _ in range(m)]
        total = 0

        for i in range(m):
            for j in range(n):

                if i == 0:
                    dp[i][j] = matrix[0][j]

                elif j == 0:
                    dp[i][j] = matrix[i][0]

                else:
                    if matrix[i][j] == 1:
                        dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j])

                total += dp[i][j]

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

    int solve( vector<vector<int>>&mat , int n , int m , vector<vector<int>>&dp){

        if(n<0 or m<0 or mat[n][m] == 0 )
            return 0;

        if(dp[n][m] != -1 )
            return dp[n][m];

        return dp[n][m] = ( 1 + min({
            solve( mat , n-1 , m , dp ),
            solve(mat , n-1 , m-1 , dp ),
            solve(mat , n , m-1 , dp )
        }));

    }

    int countSquares(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        int ans = 0 ;

        // vector<vector<int>>dp(n , vector<int>(m,-1));
        // for(int i = 0 ; i<n ; ++i ){
        // for(int j= 0 ; j<m ; ++j ){
        // ans += solve( matrix,i , j , dp );
        // }
        // }

        vector<vector<int>>dp(n , vector<int>(m, 0));

        for(int i = 0 ; i<n ; ++i ){
            for(int j = 0 ; j<m ; ++j ){
                if(i==0 || j ==0 ){
                    dp[i][j] = matrix[i][j];
                }
                else{
                    if(matrix[i][j])
                        dp[i][j] = 1 + min({dp[i-1][j] , dp[i-1][j-1] , dp[i][j-1]});
                }
            }
        }

        for(auto x : dp ){
            for(auto y : x )
                ans += y;
        }

        return ans ;
    }
};
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var countSquares = function(matrix) {
  let count = 0;
  for (let i = 0; i < matrix.length; ++i) {
    for (let j = 0; j < matrix[0].length; ++j) {
      if (matrix[i][j] === 0) continue;
      if (i > 0 && j > 0) {
        matrix[i][j] += Math.min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]);
      }
      count += matrix[i][j];
    }
  }
  return count; 
};
Count Square Submatrices with All Ones