最大正方形（难度：中等）

该题对应力扣网址

思路

min_value=min({dp[i-1][j-1],dp[i-1][j],dp[i][j-1]})
dp[i][j]+=min_value

关键点是正方形的右下角(n>1时)，通过画图，可以看出，在基础正方形2×2中，当右下角=1，且其余三块不=0时
以右下角这个小正方形作为可能组成的大正方形的右下角时，那么可能组成的大正方形的边长，就是其他三块的最小边长+它本身的边长
其中，其他三块中每一块的边长指的是，以每一块作为正方形右下角时的最小边长。

AC代码

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int m=matrix.size();int n=matrix[0].size();int flag=0;vector <vector<int>> dp(m,vector<int>(n));//初始化dp数组for(int i=0;i<m;i++){for(int j=0;j<n;j++){dp[i][j]=matrix[i][j]-'0';}}if(m==1 && n==1){if(matrix[0][0]=='0'){return 0;}return 1;}if(m==1 && n==2){if(matrix[0][0]=='1' || matrix[0][1]=='1'){return 1;}return 0;}if(m==2 && n==1){if(matrix[0][0]=='1' || matrix[1][0]=='1'){return 1;}return 0;}int min_value;int max_value=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(dp[i][j]!=0){if(i>0 && j>0){min_value=min({dp[i-1][j-1],dp[i-1][j],dp[i][j-1]});if(min_value!=0){dp[i][j]+=min_value;}}}if(dp[i][j]>max_value){max_value=dp[i][j];}}}return pow(max_value,2);}
};