221.最大正方形

动态规划

• dp[i][j]是以(i,j)为右下角的只包含1的正方形的边长的最大值
• 针对每个位置(i,j):
• 元素为0，dp[i][j]=0
• 元素为1，dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
• 元素为1的边界条件，i=0或j=0时dp[i][j]=1

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m=matrix.size();
        if(m==0) return 0;
        int n=matrix[0].size();

        vector<vector<int>> dp(m,vector<int>(n,0));
        int d=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='0'){
                    dp[i][j]=0;
                }else{
                    if(i==0||j==0){
                        dp[i][j]=1;
                    }else{
                        dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                    }
                    d=max(d,dp[i][j]);
                }
            }
        }
        int area=d*d;
        return area;
    }
};
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
26
27