1277. 统计全为 1 的正方形子矩阵

解法1：比较好理解的方式

dp[i][j][k]: 以 (i, j) 为右下角，长度为k的正方形是否满足全都为1，满足则为1，不满足则为0 我们要做的就是对每个点判断一下它可能长度的正方形是不是以下几个条件：

1. 本身是否为1
2. dp [i - 1] [j] [k - 1]是否为1
3. dp [i] [j - 1] [k - 1]是否为1
4. dp [i - 1] [j - 1] [k - 1]是否为1

这几个条件画个图就明白是怎么来的了

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        if(matrix.empty()) return 0;
        int m = matrix.size();
        int n = matrix[0].size();
        int z = min(m, n) + 10;
        int dp[m][n][z], cnt = 0;
        int row = matrix.size();
        int col = matrix[0].size();

        for(int i = 0; i < row; ++i)
        {
            for(int j = 0; j < col; ++j)
            {
                dp[i][j][1] = matrix[i][j];
                if(dp[i][j][1]) ++cnt;
            }
        } 
        
        for(int i = 1; i < row; ++i)
        {
            for(int j = 1; j < col; ++j)
            {
                for(int k = 2; k <= min(i, j) + 1; ++k)
                {
                    if(matrix[i][j] && dp[i - 1][j][k - 1] && dp[i][j - 1][k - 1] && dp[i - 1][j - 1][k - 1])
                        dp[i][j][k] = 1, ++cnt;
                    else 
                        dp[i][j][k] = 0;
                }
            }
        }

        return cnt;
    }
};

解法2：其实是对上面的优化

优化是怎么来的呢？ 假设我们现在判断（2， 2）这个点，会分别判断边长为1，2，3是不是满足题意，但是如果它最大是个边长为3的正方形，边长为1，2判断出来就一定是满足的，那我们那两次判断完全就没有什么必要，只需要求出这个3，能够组成的正方形数量通过数学计算就可以得到，也就是我们可以省略掉k那一维度。 首先我们来确定以下dp[][]数组的含义是什么？ 从上面的分析可以看出，我们的主要目标就是找到那个3，也就是以(i, j)为右下角的正方形的最大边长，所以数组的含义自然就是这个。 接下来就需要确定状态转移方程，这个就是这个问题的难点，我们如何通过之前的状态推得当前的状态，之前的状态无非就是dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1], 我觉得这个时候为他们赋个值，画个图可能会好理解一些，假设它们的值依次是1， 2， 3

金色的部分就是以(i, j)为右下角的最大变成的正方形，就是从3个之前的状态中找到最小的然后+1得到的，其实也不难理解，就有种短板效应的意思，最大边长越短说明周边环境越苛刻，下一个状态需要考虑到全体情况，就需要满足最苛刻的条件，也就是3个之前状态中边长最短的那个。

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        if(matrix.empty()) return 0;
        int m = matrix.size();
        int n = matrix[0].size();
        int z = min(m, n) + 10;
        int dp[m][n], cnt = 0;
        int row = matrix.size();
        int col = matrix[0].size();

        for(int i = 0; i < col; ++i) dp[0][i] = matrix[0][i], cnt += dp[0][i];
        for(int i = 1; i < row; ++i) dp[i][0] = matrix[i][0], cnt += dp[i][0];
        
        for(int i = 1; i < row; ++i)
        {
            for(int j = 1; j < col; ++j)
            {
                if(matrix[i][j])
                {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    cnt += dp[i][j];
                }
                else 
                    dp[i][j] = 0;
            }
        }

        return cnt;
    }
};