详解 leetcode 221题：最大正方形 Leetcode 1277：统计全为 1 的正方形子矩阵

https://leetcode-cn.com/problems/maximal-square/

题目描述

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例

输入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

解法二：动态规划
对于动态规划，大部分情况下我们都会定义一个二维数组dp，然后定义dp[i][j] 的含义，接着推导 dp[i][j] 与 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 之间的关系。当然，也可以是推导 dp[i][j] 与 dp[i+1][j]、dp[i][j+1]、dp[i+1][j+1] 之间的关系，下面我们讲下用 dp 该怎么解这道题。

1、首先我们定义 dp[i][j] 含义为正方形以 dp[i][j] 作为右下角时的最大边长值。

2、接着我们来推导他们的关系

显然，对于任意一点 dp[i][j]，由于该点是正方形的右下角，所以该点的右边，下边，右下边都不用考虑，关心的是左边，上边，和左上边，也就是我们要推导 dp[i][j] 与 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 之间的关系。他们有如下关系

dp[i][j] = min( dp[i-1][j], dp[i-1][j-1], dp[i][j-1] ）+ 1

这个关系其实也不算难推，毕竟不能有 0 存在，所以只能取交他们三个点的交集。你们可以画个图，可能就比较好理解了。

代码如下：

#include<cmath>
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.size()==0 || matrix[0].size()==0) return 0;
        int row=matrix.size();
        int maxlen=0;
        int col=matrix[0].size();
        int dp[row+10][col+10];
        //或者int[][] dp = new int[rows + 10][cols + 10];好像不行。。。
        memset(dp,0,sizeof(dp));

        for (int i=1;i<=row;i++)
            for (int j=1;j<=col;j++)
            if (matrix[i-1][j-1]=='1')
            {
                dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                if (dp[i][j]>maxlen) maxlen=dp[i][j];
            }
        return maxlen*maxlen;
    }
};

时间复杂度：O(n*m)
空间复杂度：O(n*m)
 

原文链接：https://blog.csdn.net/m0_37907797/article/details/102914218

 

顺便写了一下leetcode1277  https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/

本题和 221. 最大正方形 非常类似，使用的方法也几乎相同。

我们用 f[i][j] 表示以 (i, j) 为右下角的正方形的最大边长，那么除此定义之外，f[i][j] = x 也表示以 (i, j) 为右下角的正方形的数目为 x（即边长为 1, 2, ..., x 的正方形各一个）。在计算出所有的 f[i][j] 后，我们将它们进行累加，就可以得到矩阵中正方形的数目。

#include<cmath>
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        if (matrix.size()==0 || matrix[0].size()==0) return 0;
        int row=matrix.size();
        int ans=0;
        int col=matrix[0].size();
        int dp[row+10][col+10];
        //int[][] dp = new int[rows + 10][cols + 10];
        memset(dp,0,sizeof(dp));

        for (int i=1;i<=row;i++)
            for (int j=1;j<=col;j++)
            if (matrix[i-1][j-1]==1)
            {
                dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                ans+=dp[i][j];
            }
        //delete[] dp;
        return ans;
    }
};