給一個由 0 1 組成的矩陣，回傳有多少個正方形全部都是 1 。
這題蠻容易的，就算用暴力法 + dp ，也不會被判超時。
如果本身是 1 ，自己能形成一個正方形，然後往四角延伸去看是否能構成更大的正方形。
用 y x 由上至下，由左至右，所以選右下作基準點。那麼能構成更大的正方形，是其左上、左、上都是同一個數字。
如構成 2 * 2：
[[1,1],
[1,2]]
位置[1][1]的點，其左上、左、上都是 1 ，所以可以構成 2(1+1)。
3 * 3：
[[1,1,1],
[1,2,2],
[1,2,3]]
位置[2][2]的點，其左上、左、上都是 2 ，所以可以構成 3(2+1)。3 表示該位置有(1*1、2*2、3*3)的正方形。
位置[2][1]的點，其左上2、左1、上1，所以可以構成 2(1+1)。
也就是說，是左上、左、上中取最小值+1。前提也要該位置本來是 1 才可以這樣處理。
Python
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
result = 0
cols = len(matrix[0])
for y in range(len(matrix)):
for x in range(cols):
if matrix[y][x] == 1:
if y - 1 >= 0 and x - 1 >= 0:
matrix[y][x] = min(matrix[y-1][x-1], matrix[y][x-1], matrix[y-1][x]) + 1
result += matrix[y][x]
return result
C#
public class Solution {
public int CountSquares(int[][] matrix) {
int result = 0;
for(int y = 0; y < matrix.Length; y++)
{
for(int x = 0; x < matrix[0].Length; x++)
{
if(matrix[y][x] == 1)
{
if(y >= 1 && x >= 1)
{
matrix[y][x] = 1 + Math.Min(matrix[y-1][x], Math.Min(matrix[y-1][x-1], matrix[y][x-1]));
}
result += matrix[y][x];
}
}
}
return result;
}
}