LeetCode 85. Maximal Rectangle

题目

此题目动态规划可以解

在矩阵上一层一层递推。

dp[i][j]表示当前层，从i到j 可以形成矩形的最大面积。

需要有两个DP数组，dp[i][j] 和dp2[i][j] , 在递推的过程相互轮换。dp[i][j]表示上一层的状态数组，dp2[i][j]表示当前层的状态数组

状态转移方程是

if(matrix[I...j]=1)
dp2[i][j] = dp[i][j] + j-i+1;
else
dp2[i][j] = 0

c++

class Solution {
public:
    int dp[195][195];
    int dp2[195][195];
    int maximalRectangle(vector<vector<char>>& matrix) {
        
        int n=matrix.size();
        if(n==0)
            return 0;
        int m=matrix[0].size();
        
        if(m==0)
            return 0;
        
        int ans=0;
        
        for(int i=0;i<m;i++)
        {
            if(matrix[0][i]=='1')
            {
                dp[i][i]=1;
                ans=max(ans,dp[i][i]);
                for(int k=i-1;k>=0;k--)
                {
                    if(matrix[0][k]=='1')
                    {
                        dp[k][i] = i-k+1;
                        ans=max(ans,dp[k][i]);
                    }
                    else
                        break;
                }
            }
        }
        
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(matrix[i][j]=='1')
                {
                    if(dp[j][j]!=0)
                    {
                        dp2[j][j] = dp[j][j]+1;
                        ans=max(ans,dp2[j][j]);
                    }
                    else
                    {
                        dp2[j][j]=1;
                        ans=max(ans,dp2[j][j]);
                    }
                    
                    for(int k=j-1;k>=0;k--)
                    {
                        if(matrix[i][k]=='1')
                        {
                            if(dp[k][j]!=0)
                            {
                                dp2[k][j] = dp[k][j] + j-k+1;
                            }
                            else
                            {
                                dp2[k][j] = j-k+1;
                            }
                            
                            ans=max(ans,dp2[k][j]);
                        }
                        else
                            break;
                    }
                }
              
            }
            
            for(int p=0;p<m;p++)
            {
                for(int q=p;q<m;q++)
                {
                    
                    dp[p][q]=dp2[p][q];
                    dp2[p][q]=0;
                }
            }
            
        }
        
        return ans;
        
    }
};