LEETCODE ALGORITHM:221. Maximal Square

发表于 更新于 分类于 Waline： 阅读次数：

题目

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:

1
2
3
4
5
6
7
8
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[i][j]=min\{dp[i-1][j-1],dp[i-1][j],dp[i][j-1]\}+1 \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size()==0) return 0;
        int ans=0;
        vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size()));
        for(int i=0;i<matrix.size();++i)
        {
            for(int j=0;j<matrix[0].size();++j)
            {
                if(i==0||j==0)
                {
                    dp[i][j]=matrix[i][j]-'0';
                    if(matrix[i][j]=='1') ans=max(ans,1);
                }else{
                    if(matrix[i][j]=='1') dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                    else dp[i][j]=0;
                    ans=max(ans,dp[i][j]);
                }
            }
        }
        //return dp[2][3];
        return ans*ans;
    }
};