最大正方形

首先說一下暴力方法，就是對于每一個元素，如果是1，那么就判斷他的左上角是不是1,如果是，就擴展這個正方形，查看對應的一列和一行是不是全都是1,如果是就繼續擴展

暴力法

雖然說我用的是動態規劃，但是本質上還是暴力搜索

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        //dp[i][j]表示以(i,j)為右下角的正方形的最大面積
        //掛羊頭賣狗肉，其實本質還是暴力搜索
        
        int ans = 0;
        for(int i = 0;i < matrix.size();i++){
            for(int j = 0;j < matrix[0].size();j++){
                if(matrix[i][j] == '1'){
                    ans = 1;
                    break;
                }
            }
        }
        vector<vector<int>> dp(matrix.size());
        for(int i = 0;i < matrix[0].size();i++)dp[0].push_back(matrix[0][i] - '0');
        for(int i = 1;i < matrix.size();i++)dp[i].push_back(matrix[i][0] - '0');
        for(int i = 1;i < matrix.size();i++){
            for(int j = 1;j < matrix[i].size();j++){
                if(matrix[i][j] == '0'){
                    dp[i].push_back(0);
                }
                else{
		    //這里的k表示左上角的最大正方形面積的邊長
                    int k = sqrt(dp[i - 1][j - 1]);
                    bool flag = true;
                    //使得每次k減小1,為的就是防止正方形重疊的情況
                    while(k > 0){
                        flag = true;
                        for(int m = 1;m <= k;m++){
                            if(dp[i][j - m] == 0)flag = false;
                        }
                        for(int m = 1;m <= k;m++){
                            if(dp[i - m][j] == 0)flag = false;
                        }
                        if(flag == true)break;
                        k--;
                    }
                    if(flag)dp[i].push_back((k + 1) * (k + 1));
                    else dp[i].push_back(1);
                }
                ans = max(ans,dp[i][j]);
            }
        }
        return ans;
    }
};

這種做法有一個坑，就是這個例子

[["0","0","0","1"],["1","1","0","1"],["1","1","1","1"],["0","1","1","1"],["0","1","1","1"]]

存在正方形重疊的問題，所以才有了對k的迭代，每次使得k減1,從而獲取最小邊長

動態規劃

這才是正確解法，暴力搜索的方式效率太低了
首先定義dp[i][j]表示以(i,j)結尾的最大正方形邊長，有如下遞推公式
dp[i][j] = min(dp[i - 1][j],dp[i][j - 1],dp[i - 1][j - 1]) + 1

可以理解為從當前位置的左面，上面，左上選擇最小的那個正方形，然后+1

為什么是最小呢？

我們可以看到，為了能夠構成正方形，我們選擇最小的那個正方形，那么另外兩個比較大的矩形是一定可以覆蓋到這個的，所以可以保證一定能構成正方形

推導過程可以看這里1277. 統計全為 1 的正方形子矩陣

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int ans = 0;
        vector<vector<int>>dp(matrix.size());
        for(int i = 0;i < matrix.size();i++)dp[i].push_back(matrix[i][0] - '0');
        for(int i = 1;i < matrix[0].size();i++)dp[0].push_back(matrix[0][i] - '0');
        for(int i = 1;i < matrix.size();i++){
            for(int j = 1;j < matrix[0].size();j++){
                if(matrix[i][j] == '0')dp[i].push_back(0);
                else dp[i].push_back(min(min(dp[i - 1][j],dp[i][j - 1]),dp[i - 1][j - 1]) + 1);
            }
        }
        for(int i = 0;i < dp.size();i++){
            for(int j = 0;j < dp[0].size();j++){
                ans = max(ans,dp[i][j]);
            }
        }
        return ans * ans;
    }
};