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


  • 0
    H
    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;
        }
    };

Log in to reply
 

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