題目： LeetCode - 221. Maximal Square

題目說明

給一個二維陣列，裡面包含 0 和 1，求出其中值為 1 的元素能組出的最大正方形。

解題思路

對於陣列中的每個元素來說，若該值為 1，能組出的最大正方形的長度為，左邊那個元素能組出的最大正方形的長度、上面那個元素能組出的最大正方形的長度 和 左上角那個元素能組出的最大正方形的長度，三者的最小值 + 1，依照此想法使用動態規劃即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int height = matrix.size();
        if(!height)
            return 0;
        int width = matrix[0].size(), Max = 0;
        auto dp = vector<vector<int>>(height + 1, vector<int>(width + 1, 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][j - 1], dp[i - 1][j - 1])) + 1,    Max = max(Max, dp[i][j]);
        return Max * Max;
    }
};