题解 | 最大正方形

class Solution {
public:
    /**
        用另一个矩阵，记录以这个位置为右下角的最大正方形的边得数量，动态规划
     */
    int solve(vector<vector<char> >& matrix) {
        if(matrix.size() == 0){
            return 0;
        }

        vector< vector<int> > dp( matrix.size()+1, vector<int>(matrix[0].size()+1, 0));  //因为有边界情况，左边和上边进行扩展一行，初始化边为0；不用再进行边界分类讨论；
        int maxlen=0;
        for(int i=1; i<dp.size(); i++){
            for(int j=1; j<dp[0].size(); j++){
                if(matrix[i-1][j-1]=='0'){  //dp数组和matrix的位置关系；
                    dp[i][j]=0;
                }else{
                    dp[i][j] = min( dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]) )+1;
                    maxlen = max(maxlen, dp[i][j]);
                }
            }
        }

        return maxlen*maxlen;
    }
};