(DP 线性DP) leetcode 221. Maximal Square

佚名 5年前 (2019-05-10) 随笔 1750人围观抢沙发百度已收录

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

Example:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input: 

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

Output: 4

===============================================================

这是一个DP题，好像是线性DP吧。

官方题解有DP的题解，https://leetcode.com/articles/maximal-square/ 大家可以看看，不过是英文的。

也可以看看Grandyang大佬的博文：http://www.cnblogs.com/grandyang/p/4550604.html

这个题中，状态转换式为：dp[i][j] = min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1])) + 1;（当matrix[i][j] == '1'时），注意边界条件，在首行和首列中，由于只有一行，所以正方形的面积肯定为1.所以，当matrx[i][0] == '1'或matrix[0][j] == '1'时，有dp[i][0] == 1或dp[0][j] == 1。并且更新res为1.注意最后的取值中应返回其平方值，因为这是求面积的。

C++代码：

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int m = matrix.size(),n = matrix[0].size();
        vector<vector<int> > dp(m,vector<int>(n,0));
        int res = 0;
        for(int i = 0; i < m; i++){
            dp[i][0] = matrix[i][0] - '0';
            if(dp[i][0] == 1)
                res = 1;
        }
        for(int j = 0; j < n; j++){
            dp[0][j] = matrix[0][j] - '0';
            if(dp[0][j] == 1)
                res = 1;
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == '1'){
                    dp[i][j] = min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1])) + 1;
                }
                res = max(res,dp[i][j]);
            }
        }
        return res*res;
    }
};