leetcode 221. Maximal Square 最大正方形面积 + 动态规划DP实现

淩亂°似流年 2022-06-08 11:55 177阅读 0赞

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0  
1 0 1 1 1  
1 1 1 1 1  
1 0 0 1 0  
Return 4.

原以为是DFS深度优先遍历，后来一想，这个是求最大的**正方形**的面积，DFS似乎解决不了问题。后来我一直想着使用DFS解决问题，但是想不出来，后来网上看到了一个DP做法，这个方法十分的棒。

**这个一个很基本的动态规划DP的做法，必须要会做**

**主要思路如下：**当我们判断以某个点为正方形右下角时最大的正方形时，那它的上方，左方和左上方三个点也一定是某个正方形的右下角，否则该点为右下角的正方形最大就是它自己了。这是定性的判断，那具体的最大正方形边长呢？我们知道，该点为右下角的正方形的最大边长，最多比它的上方，左方和左上方为右下角的正方形的边长多1，最好的情况是是它的上方，左方和左上方为右下角的正方形的大小都一样的，这样加上该点就可以构成一个更大的正方形。

但如果它的上方，左方和左上方为右下角的正方形的大小不一样，合起来就会缺了某个角落，这时候只能取那三个正方形中最小的正方形的边长加1了。

s假设dpi表示以i,j为右下角的正方形的最大边长，则有

**dp\[i\]\[j\] = min(dp\[i-1\]\[j-1\], dp\[i-1\]\[j\], dp\[i\]\[j-1\]) + 1**  
**dp\[i\]\[j\]表示已（i，j）为右下角的正方形的最大的边长**

代码如下：

/*
     * 当我们判断以某个点为正方形右下角时最大的正方形时，那它的上方，左方和左上方三个点也一定
     * 是某个正方形的右下角，否则该点为右下角的正方形最大就是它自己了。这是定性的判断，
     * 那具体的最大正方形边长呢？我们知道，该点为右下角的正方形的最大边长，最多比它的上方，
     * 左方和左上方为右下角的正方形的边长多1，最好的情况是是它的上方，左方和左上方为右下角的
     * 正方形的大小都一样的，这样加上该点就可以构成一个更大的正方形。 
     * 
     * 但如果它的上方，左方和左上方为右下角的正方形的大小不一样，合起来就会缺了某个角落，
     * 这时候只能取那三个正方形中最小的正方形的边长加1了。
     * s假设dpi表示以i,j为右下角的正方形的最大边长，则有
     * dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
     * 
     * dp[i][j]表示已（i，j）为右下角的正方形的最大的边长
     * 
     * */
    public class Solution 
    {
        public int maximalSquare(char[][] matrix) 
        {
        
            if(matrix==null || matrix.length<=0)
                return 0;
            int [][]dp=new int[matrix.length][matrix[0].length];
            //注意res的初始化
            int res=0;
            for(int i=0;i<matrix.length;i++)
            {
        
                if(matrix[i][0]=='1')
                {
        
                    dp[i][0]=1;
                    res=1;
                }else
                    dp[i][0]=0;     
            }
            for(int i=0;i<matrix[0].length;i++)
            {
        
                if(matrix[0][i]=='1')
                {
        
                    dp[0][i]=1;
                    res=1;
                }else
                    dp[0][i]=0;
            }
    
            for(int i=1;i<matrix.length;i++)
            {
        
                for(int j=1;j<matrix[0].length;j++)
                {
        
                    if(matrix[i][j]=='0')
                        dp[i][j]=0;
                    else 
                    {
        
                        dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j],dp[i][j-1])) + 1;
                        res = Math.max(res, dp[i][j]);
                    }
                }
            }     
            //因为res是最大边长，所以边长的平方就是面积
            return res*res;
        }
    }

下面是C++的做法，就是一个简单的DP，很棒的做法

代码如下：

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        int maximalSquare(vector<vector<char>>& mat)
        {
            if (mat.size() <= 0)
                return 0;
            int res = 0;
            vector<vector<int>> dp(mat.size(), vector<int>(mat[0].size(), 0));
            for (int i = 0; i < mat.size(); i++)
            {
                if (mat[i][0] == '1')
                {
                    dp[i][0] = 1;
                    res = 1;
                }
                else
                    dp[i][0] = 0;
            }
            for (int i = 0; i < mat[0].size(); i++)
            {
                if (mat[0][i] == '1')
                {
                    dp[0][i] = 1;
                    res = 1;
                }
                else
                    dp[0][i] = 0;
            }
    
    
            for (int i = 1; i < mat.size(); i++)
            {
                for (int j = 1; j < mat[0].size(); j++)
                {
                    if (mat[i][j] == '1')
                    {
                        dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
                        res = max(res, dp[i][j]);
                    }
                    else
                        dp[i][j] = 0;
                }
            }
    
            return res*res;
    
        }
    };