221. 最大正方形

1. 背

这道题是dp，每个点代表以这个点为右下角点的正方形能够满足要求的值。
dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
具体为啥，这个就比较麻烦了用两个不等式联立的。

首先考虑dp[i[j]，假设正方形大小是4，因为dp[i][j]=4，所以dp[i-1][j]、dp[i][j-1]和dp[i-1][j-1]最小是3，因为如果它们胆敢小于3，那么它们肯定会有部分有0，那么dp[i][j]肯定就不是4了。
f[i][j - 1] >= f[i][j] - 1
f[i - 1][j] >= f[i][j] - 1
f[i - 1][j - 1] >= f[i][j] - 1
三个不等式联立：
min(f[i][j−1],f[i−1][j],f[i−1][j−1])≥f[i][j]−1

再考虑另外三个点，如果这三个点是3，那么dp[i][j]至少是4，如果有一个是胆敢是3，那么就说明另外的三个点肯定有一个里面有0。
因此
f[i][j]≥min(f[i][j−1],f[i−1][j],f[i−1][j−1])+1
所以f[i][j]=min(f[i][j−1],f[i−1][j],f[i−1][j−1])+1

2. 题目

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

示例 1：

输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：4
示例 2：

输入：matrix = [[“0”,“1”],[“1”,“0”]]
输出：1
示例 3：

输入：matrix = [[“0”]]
输出：0

3. 答案

class Solution {
public:
    int maximalSquare(vector>& matrix) {
	int row = static_cast(matrix.size());
	int cal = static_cast(matrix[0].size());
	vector>dp(row,vector(cal,0));
	dp[0][0] = matrix[0][0]=='1'?1:0;
	int ret = dp[0][0];
	for(int i=0;i=0?dp[i-1][j]:0;
                int left = j-1>=0?dp[i][j-1]:0;
                int left_up = i-1>=0 && j-1>=0?dp[i-1][j-1]:0;
                dp[i][j] = min(min(up,left),left_up)+1;
                ret = max(ret,dp[i][j]);
            }
		}
	}
	return ret*ret;

    }
};
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
28
29