题目描述：在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
eg:
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4思路描述：这道题最直观的解法就是每次找到一个入口之后（也就是1），然后像下方和右方扩散，每次检查是否存在一行以及一列 1 ，存在的话更新最大正方形的边长。但是时间复杂度太高，因为遍历整个二维矩阵就要 O(mn)，然后每次还要去判断一下新增的一行一列是否均为 1。
比如
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0首先可以看出来只有第2行第3列开始才可以进行扩散了，先看下面两个和右边两个是否均为 1，是
再看下面三个和右边三个是否均为 1，不是，那么更新最大边长为 2。
我们这里就不实现这种方法了，我们看一下另一种比较好的思路，动态规划。
如果我们使用 dp[i,j] 表示以 (i,j) 为右下角的正方形的边长的最大值。为什么是右下角呢？因为我们是正着遍历的，如果你想要倒着遍历，那就是左上角了。
那么如果 matrix[i][j] == 0，dp[i][j] = 0，因为题目要求的正方形应该是全 1 的
如果 matrix[i][j] == 1，那么我们想想如果 (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();
int ans = 0;
vector<vector<int>> dp(m, vector<int>(n, 0));
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++){
if(matrix[i][j] == '1'){
if(i == 0 || j == 0) dp[i][j] = 1;
else dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i- 1][j - 1])) + 1;
ans = max(ans, dp[i][j]);
}
}
return ans*ans;
}
};就和我之前说过的一样，动态规划的空间复杂度一般都可以进行降维处理，我们看一下自己的递推式，其实只是用到了上一层的 dp[i-1][j-1] 和上一层的 dp[i-1][j]，所以我们除了存储一行数据之外，只需要再找一个变量存一下 dp[i-1][j-1] 就好了，dp[i-1][j]没必要存，因为更新之前它的值还是旧值。
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
if(m == 0) return 0;
int n = matrix[0].size();
int ans = 0, cross = 0;
vector<int> dp(n, 0);
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++){
int temp = dp[j];
if(matrix[i][j] == '1'){
if(i == 0 || j == 0) dp[j] = 1;
else dp[j] = min(dp[j], min(dp[j - 1], cross)) + 1;
ans = max(ans, dp[j]);
}else dp[j] = 0;
cross = temp;
}
return ans*ans;
}
};