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

Example 1:

```Input: matrix =
[
[0,1,1,1],
[1,1,1,1],
[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.
```

Constraints:

• `1 <= arr.length <= 300`
• `1 <= arr.length <= 300`
• `0 <= arr[i][j] <= 1`

Idea:

Dynamic Programing

• dp[i][j] := edge of largest square with bottom right corner at (i, j)
• base case:
• dp, dp[i], dp[j] = 1 if martix[i][j] = 1
• The current unit can form the largest square matrix with the left, upper and upper left units. For example, a unit can form a matrix with a side length of 3 with the left, top, and top left units. That can also form a matrix with a side length of 2 and a side length of 1. So:
• dp[i][j] = min(dp[i – 1][j], dp[i – 1][j – 1], dp[i][j – 1])+1 if matrix[i][j] == 1 else 0
• ans = sum of all dp[i][j]

Solution:

``````/**
* @param {number[][]} matrix
* @return {number}
*/
var countSquares = function(matrix) {
let row = matrix.length;
let col = matrix.length;
let dp = Array.from(new Array(row), () => new Array(col));
let sum = 0;
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
// Basic cases:
// dp, dp[i], dp[j] cases => has 1, form a square
dp[i][j] = matrix[i][j];

if (i && j && dp[i][j]) // Why? See Above
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1;

sum += dp[i][j];
}
}
return sum;
};``````