题解 | #最大正方形#

动态规划：
第一，使用二维数组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;
    }
};