题解 | #最大正方形#

动态规划：

class Solution {
public:
    /**
     * 最大正方形
     * @param matrix char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& matrix) {
        // write code here
        int height = matrix.size(), width = matrix[0].size();
        vector<vector<int> > dp(height+1, vector<int>(width+1, 0));
        int maxside = 0; //正方形最大边
        for (int i = 1; i <= height; i++) {
            for (int j = 1; j <= width; j++) {
                if (matrix[i-1][j-1] == '1') {
                    //递推公式
                    dp[i][j] = min(dp[i-1][j], min(dp[i-1][j-1], dp[i][j-1])) + 1;
                    maxside = max(maxside, dp[i][j]);
                }
            }
        }
        return maxside*maxside;
     }
};