# My DP solution(c++,状态压缩)

• ``````class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if(m==0) return 0;
int n = matrix[0].size();
//bool dp[m][n][m+1][n+1];
bool dp[2][n+1];
int maxRectangle = 0;
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
if(matrix[i][j] == '0') continue;
for(int xLen = 1;i+xLen-1 < m;xLen++){
for(int yLen = 1;j+yLen-1 < n;yLen++){
if(matrix[i+xLen-1][j+yLen-1] == '0') {
dp[0][yLen] = false;
break;
}
if(xLen == 1 && yLen == 1)
//dp[i][j][xLen][yLen] = true;
dp[1][yLen] = true;
else if(xLen == 1 && yLen != 1){
//dp[i][j][xLen][yLen] = dp[i][j][xLen][yLen-1];
dp[1][yLen] = dp[1][yLen-1];
}else if(xLen != 1 && yLen == 1){
dp[1][yLen] = dp[0][yLen];
}else{
dp[1][yLen] = dp[1][yLen-1] && dp[0][yLen];
}
if(dp[1][yLen]) {maxRectangle = max(xLen * yLen,maxRectangle);
dp[0][yLen] = dp[1][yLen];}
else break;
}
}
}
}
return maxRectangle;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.