題目
在一個(gè)由 0 和 1 組成的二維矩陣內(nèi)馍佑，找到只包含 1 的最大正方形吝镣，并返回其面積亦歉。
示例:
輸入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
輸出: 4
解題思路
使用動(dòng)態(tài)規(guī)劃的思想淳附，對(duì)于matrix[i][j]對(duì)應(yīng)的dp[i][j]表示i帮辟，j作為正方形的右下角的正方形邊長(zhǎng)打洼，當(dāng)dp[i-1][j]龄糊、dp[i][j-1]、dp[i-1][j-1]存在零的時(shí)候募疮，dp[i][j]為matrix[i][j]的值炫惩，當(dāng)都不為零時(shí)，dp[i][j] 為三個(gè)值中最小的值+1阿浓。
代碼
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.size() == 0) return 0;
int dp[matrix.size()][matrix[0].size()] = {0};
int maxRec = 0;
//初始化
for(int i=0; i < matrix.size(); i++){
dp[i][0] = matrix[i][0] - '0';
maxRec = max(matrix[i][0] - '0', maxRec);
}
for(int j = 0; j < matrix[0].size();j++){
dp[0][j] = matrix[0][j] - '0';
maxRec = max(matrix[0][j]-'0', maxRec);
}
//開(kāi)始查找
for(int i=1; i < matrix.size(); i++){
for(int j=1; j < matrix[0].size(); j++){
if(matrix[i][j] == '1'){
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
maxRec = max(dp[i][j], maxRec);
}else{
dp[i][j] = 0;
}
}
}
return maxRec*maxRec;
}
};
