[关闭]
@myecho 2019-04-16T10:34:41.000000Z 字数 5858 阅读 735

区间DP&二维DP

动态规划

区间DP一般都可以使用记忆化搜索或者直接DP的方法写。
区间DP在枚举状态时由于每次都是区间减少，所以可以使用区间l作为一维进行枚举。
由矩阵连乘拓展出来的几道习题
1. POJ 1651 Multiplication Puzzle
题意：一排牌/卡片（一串数字），每次从这些牌中拿走一张牌（首尾两张不能拿），把前一张，这一张，后一张牌上的数字相乘的结果累加，直到只剩下两张牌为止。问所能得到的最小结果是多少。

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<string>
  4. using namespace std;
  5. int a[101];
  6. int m[101][101];
  7. #define INF 0x3f3f3f3f
  9. int main(){
  10.     int n;
  11.     cin >> n;
  12.     for(int i = 1; i <= n; ++i){
  13.         cin >> a[i];
  14.     }
  15.     for(int i = 1; i <= n; ++i){
  16.         m[i][i] = 0;
  17.         m[i][i+1] = 0;    //边界还是挺重要的!
  18.     }
  19.     for(int l = 3; l <= n; ++l){
  20.         for(int i = 1; i <= n-l+1; ++i){
  21.             int j = i+l-1;
  22.             m[i][j] = INF;
  23.             for(int k = i+1; k <= j-1; ++k){ //注意k的范围
  24.                 m[i][j] = min(m[i][j], m[i][k]+m[k][j]+a[k]*a[i]*a[j]); //not a[k+1]*a[k]*a[k-1]
  25.             }
  26.         }
  27.     }
  28.     cout << m[1][n] << endl;
  29.     return 0;
  30. } //http://www.cnblogs.com/hoodlum1980/archive/2012/06/07/2540150.html
  1. uva的Cutting Sticks

所以我们必须在木棍的做左边和左右边分别添加一个点，那么得到的就是整个区间。(套模板)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 50 + 10;
const int INF = ~0U >> 2;
int w[MAXN],dp[MAXN][MAXN];
int L,n;

int solve(){
    n++;
    for(int i = 0;i <= n;++i)
        for(int j = i+1;j <= n;++j)
            dp[i][j] = (i+1 == j ? 0 : INF);

    w[0] = 0; w[n] = L;
    for(int p = 1;p <= n;++p){            //区间长度
        for(int s = 0;s <= n-p;++s){       // 起始位置
            int e = s + p;                //终点
            for(int k = s+1;k < e;++k){    //状态转移
                dp[s][e] = min(dp[s][e],dp[s][k] + dp[k][e] + w[e] - w[s]);
            }
        }
    }
    return dp[0][n];
}
int main()
{
    while(scanf("%d",&L),L){
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i){
            scanf("%d",&w[i]);
        }
        printf("The minimum cutting is %d.\n",solve());
    }
    return 0;
}
  1. poj3280
    题目链接:http://poj.org/problem?id=3280
    题目大意:给出一个字符串，并给出删除或者添加这个字符串中的字符所对应的代价，求让字符串变为回文串的最小代价。
    严格的说这个题目应该划分到有关字符串的dp题目当中。
    思路:
    dp[i][j] 表示 将 str[i-----j] 变为回文串的最小花费
    if(str[i] == str[j]) dp[i][j] = dp[i + 1][ j - 1];
    else
    {
    dp[i][j] = min(dp[i + 1][j] + min(add[str[i] - 'a'],dele[str[i ]- 'a']),dp[i][j -1] + min(add[str[j]- 'a'],dele[str[j ]- 'a'])) ;
    }
    题解:http://www.cnblogs.com/acSzz/archive/2012/08/11/2633509.html
    还是要注意dp时候的for循环决定着子问题的解决顺序。

其实dp很难逃出3种思路：
1、一维线性dp：每次考虑i时，选择最优子问题要么在i-1，要么在1...i-1里；
2、二维线性dp：考虑(i,j)子问题时，选择最优子问题要么在(i+1,j)、(i,j-1)，要么在i<= k <=j里；
3、树形dp：考虑i节点最优时，选择子节点最优，一般融合了01背包dp的双重dp。
4. LightOJ 1422 Halloween Costumes
此题比较难考虑到区间dp上来，但是题目中通过推理可以判断出类似"断点"的结构。
题目链接；http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=27130
5. poj2955 Brackets(寻求最大的括号匹配数)
题目链接:http://poj.org/problem?id=2955
递推公式:dp[i][j]= max(dp[i+1][j], dp[i+1][k-1]+dp[k][j]+2)其中i+1<=k<=j
我们可以看到从递推公式来看，和上式基本上是同一个问题。还是先找一个最差的情况，在这个题目中，dp[i+1][j]就是最差情况，然后再通过寻找一个k来划分子问题进而看是否可以优化子问题。
6. hdu 2476
题意:给出两个字符串s1,s2,通过刷这个操作，可以将s1中的某个区间内的字符全部改变为另一个字符，求问s1抓换到s2所需的最小的操作数？
需要进行两次dp操作，一次dp[i][j]统计从空串转换到s2所需的最小操作。最后一次ans[j]统计从s1转换到s2的最小的操作数。
题解:http://www.cnblogs.com/ACMDoli/articles/4676197.html

  1. 代码：#include <stdio.h>
  2. #include <string.h>
  3. #include <algorithm>
  4. using namespace std;
  6. char s1[105],s2[105];
  7. int dp[105][105];//dp[i][j]为i~j的刷法
  8. int ans[105],i,j,k,len;
  10. int main()
  11. {
  12.     while(~scanf("%s%s",s1,s2))
  13.     {
  14.         len = strlen(s1);
  15.         memset(dp,0,sizeof(dp));
  16.         for(j = 0; j<len; j++)
  17.         {
  18.             for(i = j; i>=0; i--)//j为尾，i为头
  19.             {
  20.                 dp[i][j] = dp[i+1][j]+1;//先每个单独刷
  21.                 for(k = i+1; k<=j; k++)//i到j中间所有的刷法
  22.                 {
  23.                     if(s2[i]==s2[k])
  24.                         dp[i][j] = min(dp[i][j],(dp[i+1][k]+dp[k+1][j]));//i与k相同，寻找i刷到k的最优方案
  25.                 }
  26.             }
  27.         }
  28.         for(i = 0; i<len; i++)
  29.             ans[i] = dp[0][i];//根据ans的定义先初始化
  30.         for(i = 0; i<len; i++)
  31.         {
  32.             if(s1[i] == s2[i])
  33.             {
  34.                 if(i==0)
  35.                     ans[i] = 0;
  36.                 else
  37.                     ans[i] = ans[i-1];//如果对应位置相等，这个位置可以不刷
  38.             }
  39.             else
  40.             {
  41.                 for(j = 0; j<i; j++)
  42.                     ans[i] = min(ans[i],ans[j]+dp[j+1][i]);//寻找j来分割区间得到最优解
  43.             }
  44.         }
  45.         printf("%d\n",ans[len-1]);
  46.     }
  47.     return 0;
  48. }
  1. zoj3537
    三角形的最优剖分:http://www.cnblogs.com/blackcruiser/articles/2179649.html
    也是可以通过通过选择中间节点k,来划分这个三角形。即将i与k连边，j也与k连边，剩下的左右的两部分就可以又划分成了两个子问题了。
  2. poj 2176 Folding
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #define N 110
  5. #define inf 0x7fffffff
  6. using namespace std;
  7. char str[N];
  8. struct node
  9. {
  10.     int num; //储存的是压缩后的字符串的长度
  11.     char s[N];
  12. }dp[N][N];
  14. int pos;
  15. char ts[N];
  17. void Int2S(int num)
  18. {
  19.     int i,j;
  20.     pos=-1;
  21.     char cc;
  22.     while(num)
  23.     {
  24.         ts[++pos]=(num%10)+'0';
  25.         num/=10;
  26.     }
  27.     for(j=0;j<=pos/2;j++)
  28.     {
  29.         cc=ts[j];
  30.         ts[j]=ts[pos-j];
  31.         ts[pos-j]=cc;
  32.     }
  33. }
  35. int main()
  36. {
  37.     int i,j,k,len,p,q,f,nt,t;
  38.     scanf("%s",str);
  39.     len=strlen(str);
  40.     for(i=0;i<len;i++)
  41.     {
  42.         dp[i][i].s[0]=str[i];
  43.         dp[i][i].s[1]='\0';
  44.         dp[i][i].num=1;
  45.     }
  46.     for(p=1;p<len;p++)
  47.     for(i=0;i<len-p;i++)
  48.     {
  49.         j=i+p;
  50.         dp[i][j].num=inf;
  51.         //开始处理i->j片段内的字符串如何进行打包操作
  52.         for(k=1;k<p;k++)
  53.         {
  54.             if((p+1)%k)//以k为长度进行分割
  55.             continue;
  56.             q=i+k,t=i;
  57.             while(q<=j)
  58.             {
  59.                 if(str[q]!=str[t])
  60.                 break;
  61.                 q++;
  62.                 t++;
  63.                 if(t==i+k)
  64.                 t=i;
  65.             }
  66.             if(q>j)
  67.             {
  68.                 nt=(p+1)/k;
  69.                 Int2S(nt);
  70.                 strcpy(dp[i][j].s,ts); //最好不直接拷贝，长度无法确定
  71.                 dp[i][j].s[++pos]='(';
  72.                 for(t=0;dp[i][i+k-1].s[t];t++)//将子结构中的最优片段拷贝过来 不能直接拷贝原来的字符串，因为子结构可能完成了压缩
  73.                     dp[i][j].s[++pos]=dp[i][i+k-1].s[t];
  74.                 dp[i][j].s[++pos]=')';
  75.                 dp[i][j].num=pos+1;
  76.                 dp[i][j].s[++pos]='\0';
  77.                 break;
  78.             }
  79.         }
  80.         //递推子结构中的最优结果
  81.         for(k=i;k<j;k++)
  82.         {
  83.             if(dp[i][j].num>dp[i][k].num+dp[k+1][j].num)
  84.             {
  85.                 dp[i][j].num=dp[i][k].num+dp[k+1][j].num;
  86.                 strcpy(dp[i][j].s,dp[i][k].s);
  87.                 strcat(dp[i][j].s,dp[k+1][j].s);//会将前边的'\0'覆盖
  88.             }
  89.         }
  90.     }
  91.     printf("%s\n",dp[0][len-1].s);
  92.     return 0;
  93. }

其共同特点是若A，若B，则AB，都可以将区间的问题通过划分为更小的区间来进行解决，这里需要注意不同问题之间的区别和练习，以及边界条件的处理。

二维DP(较难)
例题 URAL 1900 Brainwashing Device

  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  7. const int N=555;
  8. const int INF=1e9;
  9. int dp[N][N], pt[N][N];
  10. int c[N][N], g[N][N];
  11. int n, k;
  12. /*
  13. 输入[i][j]即为从i上车,从j下车的乘客数量，从i到j的乘客是需要途径i与j之间的中间车站的
  14. 关键在于认识到是如何划分成子问题的！
  15. */
  16. void pts(int r, int st)  //二维DP的路径一般也要使用二维数组进行保存
  17. {
  18.     if(st == 0) return;
  19.     pts(pt[r][st], st - 1);
  20.     cout<<r-1;
  21.     if(st == k) cout<<"";
  22.     else cout<<" ";
  23. }
  25. int main(){
  26.     memset(c,0,sizeof(c));
  27.     cin>>n>>k;
  28.     for(int i=1;i<n;++i){
  29.         for(int j=i+1;j<=n;++j){
  30.             cin>>c[i][j];
  31.             c[i][j]+=c[i][j-1]; //相当于输入的每一行前缀之和
  32.         }
  33.     }
  34.     for(int i=1;i<n;++i){
  35.         for(int j=i+1;j<=n;++j){
  36.             g[i][j]=0;          //g[i][j]代表第i条边到第j条边且在j-1到j之间安装装置产生的happy人数
  37.             for(int t=i;t<j;t++){
  38.                 g[i][j]+=c[t][n]-c[t][j-1];//依次添加的是 从i到j j+1 ... n车站的乘客人数
  39.             }
  40.         }
  41.     }
  42.     memset(dp,-1,sizeof(dp));//非负数，数据可能为0
  43.     dp[1][0]=0;//初始状态
  44.     for(int i=1;i<=n;++i){
  45.         for(int j=i+1;j<=n;++j){
  46.             for(int t=1;t<=min(i,k);++t){ //min(i,k)要注意
  47.                 if(dp[j][t]<dp[i][t-1]+g[i][j]){
  48.                     dp[j][t]=dp[i][t-1]+g[i][j];
  49.                     pt[j][t]=i;
  50.                 }
  51.             }
  52.         }
  53.     }
  54.     int ans=-1,id;
  55.     for(int i=k+1;i<=n;i++){
  56.         if(dp[i][k]>ans){
  57.             ans=dp[i][k];
  58.             id=i;
  59.         }
  60.     }
  61.     cout<<ans<<endl;
  62.     pts(id,k);
  63.     return 0;
  64. }

区间dp做的时候都会在for i 与for j 之后for k 之前添加dp[i][j]= INF(取最小值)或者0(需要取最大值时)之类的东西，防止无法开始比较。得不到初值.

还要注意的一点是题目中的循环顺序，我们可以发现当[i,j]时一定要求[i,k] [k,j]其中子问题的两个问题区间都比原问题的区间要小，因此最外层的循环一般是设置l，l为长度，第二层循环为i(0~n-l),j直接由l和i计算得出。从而保证所有的长度小的子问题已经得到了解决。

矩阵中最大的1
http://www.voidcn.com/article/p-vpbybrua-qz.html
s[i][j] <- s[i-1][j],s[i][j-1],s[i-1][j-1] 得到当前的最优解

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注