蓝桥杯零基础冲过赛-第11天

蓝桥杯零基础冲过赛-第11天

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

思考：这道题首先确认用DP，根据题意定义状态为dp[i][j] 为在i行j列处的最大正方形
第一步：假设

假设一个4 x 4 的数组全都是“1”

「 1 1 1 1
   1 1 1 1 
   1 1 1 1
   1 1 1 1」

那么dp[i][j]数组为

「1 1 1 1
 1 4 4 4
 1 4 9 9
 1 4 9 16」

可以发现每个值都是某个数的平方。一个位置无论在什么方向加一个位置都会使这个位置的正方形大小增大平方，比如就dp[1][1]这个位置，在dp[0][1]或dp[1][0]或dp[0][0]这三个方向任意一位置存在一个“1”都会使正方形变成平方倍，因为加的这个位置后会使边长加一，所以我们只要算他的边长就可以了。因此dp[i][j] 为在i行j列处的最大正方形这个状态定义使成平方变化的，不利于DP的状态转移，所以定义状态为为dp[i][j] 为在i行j列处的最大正方形的根号

那么根号dp[i][j]

「1 1 1 1
 1 2 2 2
 1 2 3 3
 1 2 3 4」

观察上面规律得状态转移为：
dp[i][j] = min{dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]} + 1
边界条件为：
dp[i][j] = 0;
编码：

int maximalSquare(vector>& matrix) {
        int m = matrix.size();
        if(m < 1) return 0;
        int n = matrix[0].size();
        int _max = 0;
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof(dp));
        
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]));
                    _max = max(_max, dp[i][j]); 
                }
            }
        }
        
        return _max * _max;
    }