本文共 4174 字，大约阅读时间需要 13 分钟。

分析：

这一题需要使用两次dp。第一次dp需要找到所有回文子串，第二次dp需要找到最小切。而实际上，两个dp可以同时进行。

首先是找出所有的回文子串：

设dp[j][i]为1时表示子串s[j,i]是一个回文串，那么有：

当s[j] == s[j], 且子串s[j,i]长度小于等于2或者dp[j+1][i-1]为１时

dp[j][i] = １

其中，当j > i时, dp[j][i] = 0。长度小于等于２这个判断要先于dp[j+1][i-1]这一判断，这样可以在最后避免越界的问题。

然后是找到最小切：

min_cut[i]表示前i个字符构成的子串中最小切的个数，其中min_cut[0] = -1

那么有：

当s[j, i]是回文串时，对于j <= i, 所有min_cut[j]+1中的最小值即为min_cut[i]

min_cut[i+1] = min(min_cut[i+1], min_cut[j]+1);

显然，这两个表达式可以同时执行，代码如下：

int minCut(string s) {    int size = s.length();    if(size == 0 || size == 1)        return 0;    vector
   
    
     > dp(size, vector
     
      (size,0));    vector
      
        min_cut(size+1, size-1);    min_cut[0] = -1;    for(int i = 0; i < size; i++)    for(int j = 0; j <= i ;j++) {        if(s[i] == s[j] && (i-j <= 1 || dp[j+1][i-1])) {            dp[j][i] = 1;            min_cut[i+1] = min(min_cut[i+1], min_cut[j]+1);        }    }    return min_cut[size];}
      
     
    
   

分析：

看到这一题，首先想到类似的,　只要将矩阵中的'0'替换为负数(如-100)，'1'替换为1，求出矩阵的最大子矩阵和就是答案。算法解释可参考我的，代码如下：

int maxSubarry(vector
   
    & v) {    int sum = 0, max = 0;    int size = v.size();    for(int i = 0; i < size; i++) {        if(sum < 0)            sum = v[i];        else            sum += v[i];        max = max>sum?max:sum;    }    return max;}int maxSumSubmatrix(vector
    
     
      >& matrix) {        int width = matrix[0].size();        int height = matrix.size();        int L = 0, R = 0;        int max = INT_MIN;        for(L = 0; L < width; L++) {            vector
      
        column(height, 0);            for(R = L; R < width; R++) {                for(int i = 0; i < height; i++)                    column[i] += matrix[i][R];                int cur_max = maxSubarry(column);                max = std::max(max, cur_max);            }        }        return max==INT_MIN?-1:max;}int maximalRectangle(vector
       
        
         >& matrix) { int height = matrix.size(); if(height == 0) return 0; int width = matrix[0].size(); vector
         
          
           > v(height, vector
           
            (width, 0)); for(int i = 0; i < height; i++) for(int j = 0; j < width; j++) { if(matrix[i][j] == '1') v[i][j] = 1; else v[i][j] = -100; } return maxSumSubmatrix(v);}
           
          
         
        
       
      
     
    
   

然后，还有另一种思路(也不是dp)，思路来源是：：求直方图中的最大矩阵。在这一题中，我们为每一行建立一个直方图，如果当前行的数值为０，那么矩阵高度为０，否则高度为连续的１的数量。最后对于每一行得到的最大矩阵求最大值即可。

代码如下，参考，侵删：

int largestRectangleArea(vector
   
     &height) {    int res = 0;    stack
    
      s;    height.push_back(0);    for (int i = 0; i < height.size(); ++i) {        if (s.empty() || height[s.top()] <= height[i]) s.push(i);        else {            int tmp = s.top();            s.pop();            res = max(res, height[tmp] * (s.empty() ? i : (i - s.top() - 1)));            --i;        }    }    return res;}int maximalRectangle(vector
     
      
        > &matrix) {    int res = 0;    vector
       
         height;    for (int i = 0; i < matrix.size(); ++i) {        height.resize(matrix[i].size());        for (int j = 0; j < matrix[i].size(); ++j) {            height[j] = matrix[i][j] == '0' ? 0 : (1 + height[j]);        }        res = max(res, largestRectangleArea(height));    }    return res;}
       
      
     
    
   

使用dp:

dp的思路实际上与前一个方法一致。

对于每一行构建一个直方图，

• height[ｉ][ｊ]记录的是(ｉ, ｊ)这个坐标为底座的直方图的高度
• left[ｉ][ｊ]记录的是这个坐标点对应的height可以延申到的最左边的位置
• right[row][col]记录的是这个坐标点对应的height可以延申到的最右边的位置+1

即：

left(i,j) = max(left(i-1,j), cur_left)

right(i,j) = min(right(i-1,j), cur_right)

matrix[i][j] == '1' 时

height(i,j) = height(i-1,j) + 1

matrix[i][j] == '0' 时

height(i,j) = 0

那么当前行中[right(i,j) - left(i,j)]*height(i,j)中最大的值就是当前直方图中的最大矩阵的面积。

遍历完所有行之后, 取出最大面积即为答案。

参考代码如下，侵删：

int maximalRectangle(vector
   
    
      > &matrix) {    if(matrix.empty()) return 0;    const int m = matrix.size();    const int n = matrix[0].size();    int left[n], right[n], height[n];    fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);    int maxA = 0;    for(int i=0; i
     
      =0; j--) {            if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);            else {right[j]=n; cur_right=j;}            }        // compute the area of rectangle (can do this from either side)        for(int j=0; j
     
    
   

转载地址：http://cwwob.baihongyu.com/