一、题目
在一个由 '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
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'
二、思路
看着感觉是动态规划，但一时半会感觉想不出来，直接问gpt了。
给出的思路也很简单，就是反复在（左，上，左上）取小并加一，验证正方形的最大边即可。本质就是以 dp[i][j] 为左下角，最大正方形的边长。
三、题解
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size(),0));
int maxValue=0;
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();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;
}
maxValue=max(dp[i][j],maxValue);
}
}
}
return maxValue*maxValue;
}
};
