动态规划:
第一,使用二维数组dp,确定其元素含义,此处dp[i][j]表示原二维数组第i行第j列位置元素作为正方形右下角构成的最大正方形边长,即该元素必然为‘1’,若为‘0’则无法构成正方形;
第二,建立状态转移方程:若matrix[i][j]为'1'时,需要检查其左、上、左上角在dp数组中的值,要构成正方形则考虑木桶效应,即该位置的值为左、上、左上角的最小值加1,dp[i][j]=Min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1;
第三,考虑初始值或者边界条件,由于dp[i][j]的值依赖于i-1和j-1,故i=0和j=0时需要单独判断,若此时原数组元素为‘1’,则dp数组值为1,否则为0.
题目要求的是最大正方形的面积,而dp数组记录的是最大正方形边长的所有值,故需要保存最大正方形边长的最大值maxLen,返回该maxLen的平方即可。
class Solution { public: /** * 最大正方形 * @param matrix char字符型vector<vector<>> * @return int整型 */ int solve(vector<vector<char> >& matrix) { // write code here //使用两维数组 int row=matrix.size(); int col=matrix[0].size(); int dp[row][col]; dp[0][0]=0;//初始化 int maxLen=0; for(int i=0;i<row;++i) { for(int j=0;j<col;++j) { if(matrix[i][j]=='1') { if(i==0 || j==0) {//由于当前i和j与i-1,j-1有关,故先确定i,j为0时的值 dp[i][j]=1; } else { int temp=min(dp[i-1][j],dp[i-1][j-1]); dp[i][j]=min(temp, dp[i][j-1])+1; /*if(dp[i][j]>maxLen) {//记录边长最大值 maxLen=dp[i][j]; }*/ maxLen=dp[i][j]>maxLen?dp[i][j]:maxLen; } } else dp[i][j]=0; } } return maxLen*maxLen; } };