leetcode 221. 最大正方形
dp[i][j]表示以(i,j)为右下角的正方形最大的边长
转态转移方程:
matrix[i][j]=='1':
dp[i][j] = 1+min( dp[i-1][j-1], min( dp[i][j-1],dp[i-1][j] ));
matrix[i][j]=='0':
dp[i][j] = 0;
先初始化行和列
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int ret = 0;
if( matrix.size()==0 ){
return 0;
}
vector<vector<int> > dp(matrix.size(), vector<int>(matrix[0].size(),0));
for(int i = 0;i < dp.size();i ++){
if( matrix[i][0] == '1' ){
dp[i][0] = 1;
}else{
dp[i][0] = 0;
}
ret = max(ret,dp[i][0]*dp[i][0]);
}
for(int i = 0;i < dp[0].size();i ++){
if( matrix[0][i] == '1' ){
dp[0][i] = 1;
}else{
dp[0][i] = 0;
}
ret = max(ret,dp[0][i]*dp[0][i]);
}
for(int i = 1;i < dp.size();i ++){
for(int j = 1;j < dp[i].size();j ++){
if(matrix[i][j]== '1'){
dp[i][j] = 1;
}else{
dp[i][j] = 0;
continue;
}
dp[i][j] += min( dp[i-1][j-1], min( dp[i][j-1],dp[i-1][j] ));
ret = max(ret,dp[i][j]*dp[i][j]);
}
}
return ret;
}
};
还没有评论,来说两句吧...