力扣_动态规划4—最大正方形

题目

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

方法

• 创建二维 $dp$ 数组，$dp[i][j]$ 表示 $(i,j)$ 为右下角时正方形的最大边长
• 当 $matrix[i][j]==1$， $dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1$
• 当 $matrix[i][j]==0$， $dp[i][j]=0$

代码

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