題目鏈接
tag：
- Medium;
- Dynamic Programming;
question:
??Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
思路：
??DP吴趴，建立一個(gè)二維dp數(shù)組婿牍，其中dp[i][j]表示到達(dá)(i, j)位置所能組成的最大正方形的邊長弟疆。我們首先來考慮邊界情況，也就是當(dāng)i或j為0的情況涵卵，那么在首行或者首列中忿项，必定有一個(gè)方向長度為1扁藕，那么就無法組成長度超過1的正方形，最多能組成長度為1的正方形吮旅，條件是當(dāng)前位置為1。邊界條件處理完了味咳，再來看一般情況的遞推公式怎么辦庇勃，對于任意一點(diǎn)dp[i][j]，由于該點(diǎn)是正方形的右下角槽驶，所以該點(diǎn)的右邊责嚷，下邊，右下邊都不用考慮掂铐，關(guān)心的就是左邊罕拂，上邊，和左上邊全陨。這三個(gè)位置的dp值suppose都應(yīng)該算好的爆班，還有就是要知道一點(diǎn)，只有當(dāng)前(i, j)位置為1辱姨，dp[i][j]才有可能大于0蛋济，否則dp[i][j]一定為0。當(dāng)(i, j)位置為1炮叶，此時(shí)要看dp[i-1][j-1], dp[i][j-1]碗旅，和dp[i-1][j]這三個(gè)位置，我們找其中最小的值镜悉，并加上1祟辟，就是dp[i][j]的當(dāng)前值了，這個(gè)并不難想侣肄，畢竟不能有0存在旧困，所以只能取交集，最后再用dp[i][j]的值來更新結(jié)果res的值即可，時(shí)間復(fù)雜度到O(n2)吼具，參見代碼如下：
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.empty() || matrix[0].empty())
return 0;
int m=matrix.size(), n=matrix[0].size(), res=0;
vector<vector<int> > dp(m, vector<int>(n, 0));
for(int i=0; i<m; ++i) {
for(int j=0; j<n; ++j) {
if(i==0 || j==0)
dp[i][j] = matrix[i][j] - '0';
else if(matrix[i][j] == '1'){
dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
}
res = max(res, dp[i][j]);
}
}
return res*res;
}
};
