区间dp

区间动态规划是从区间的角度来考虑问题的。对于每段区间，它的最优值是由几段更小的区间的最优值得到，这算是分治思想的一种应用吧。

就拿http://acm.fafu.edu.cn/problem.php?id=1502
合并石子这一题来说。要求得区间1-->n石子合并的最小花费
设dp[1][n] 为合并区间1--->n的最小花费。
区间的最后一次合并一定是1--->k 与 k+1-->n合并
所以合并区间1--->k的花费最小,和合并区间k+1--->n的花费最小，才能使得合并区间1--->n的花费最小。
所以状态转移方程为：dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); sum[i]表示前i堆石子的总个数。
方程的思想是在区间的角度上来思考问题的，一个大区间的问题转化为两个小区间的问题

 1 #include <stdio.h>
 2 const int INF = 1 << 30;
 3 const int N = 100 + 10;
 4 int dp[N][N],sum[N];
 5 int min(const int &a, const int &b)
 6 {
 7     return a < b ? a : b;
 8 }
 9 int main()
10 {
11     int n,i,j,k,z;
12     scanf("%d",&n);
13     for(i=1; i<=n; ++i)
14         for(j=1; j<=n; ++j)
15             dp[i][j] = INF;
16     for(i=1; i<=n; ++i)
17     {
18         scanf("%d",&sum[i]);
19         sum[i] += sum[i-1];
20         dp[i][i] = 0;
21     }
22     for(z=2; z<=n; ++z)//枚举区间的长度
23         for(i=1; i<=n-z+1; ++i)//枚举区间的起点
24         {
25             j = i + z - 1;
26             for(k=i; k<j; ++k)//枚举区间的断点，将区间分为两个更小的区间。
27                 dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j] - sum[i-1]);
28         }
29     printf("%d
",dp[1][n]);
30 }

View Code

poj2995 Brackets http://poj.org/problem?id=2955

给出一个括号字符串，求出一个子序列（和子串是不一样的）使得括号的匹配个数最大
区间dp，从区间的角度来思考，这题的关键应该是怎么把一个区间分为两个区间。
dp[i][j]表示区间i--->j的最大匹配个数
有两种情况
如果 for(k=i+1; k<=j; ++k) if(str[i] =='[' && ']'== str[k] || str[i]=='(' && str[k]==')')
那么dp[i][j] = max(dp[i][j], dp[i+1][k-1]+dp[k+1][j]+2) //下标可能越界，数组要开大点
匹配的括号 i AAA k BBB 将区间分为了更小的两个区间.
另一种情况是：没有一个k 使得 str[i] =='[' && ']'== str[k] || str[i]=='(' && str[k]==')'
那么dp[i][j] = dp[i+1][j] 即子序列的下标不可能从i开始，而要从i+1开始。

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 100 + 10;
 4 char str[N];
 5 int dp[N][N];
 6 int max(const int &a, const int &b)
 7 {
 8     return a > b ? a : b;
 9 }
10 int main()
11 {
12     //freopen("in.txt","r",stdin);
13     int i,j,k,z;
14     while(true)
15     {
16         gets(str+1);
17         if(str[1] == 'e')
18             break;
19         int n = strlen(str+1);
20         memset(dp, 0, sizeof(dp));
21         for(z=2; z<=n; ++z)
22             for(i=1; i<=n-z+1; ++i)
23             {
24                 j = i + z - 1;
25                 dp[i][j] = dp[i+1][j];
26                 for(k=i+1; k<=j; ++k)
27                 if(str[i] =='[' && ']'== str[k] || str[i]=='(' && str[k]==')')
28                     dp[i][j] = max(dp[i][j], dp[i+1][k-1]+dp[k+1][j]+2);
29                 //else
30                     //dp[i][j] = dp[i+1][j];   不能放在这里，因为肯定会出现不匹配的情况，这就会把之前的值给覆盖掉
31 
32             }
33         printf("%d
",dp[1][n]);
34     }
35     return 0;
36 }

View Code

poj3280 Cheapest Palindrome http://poj.org/problem?id=3280

dp[i][j] 表示将区间i--->j的字符串变为回文串的最小花费
if(str[i] == str[j])
dp[i][j] = dp[i+1][j-1];
else
dp[i][j] = min(dp[i+1][j] + 在j后面增加str[i]的花费, dp[i+1][j]+删除str[i]的花费 ,dp[i][j-1]+在i前面增加str[j]的花费, dp[i][j-1]+删除str[j]的花费);

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 2000 + 10;
 4 char str[N];
 5 struct node
 6 {
 7     int add,del;
 8 }cost[26];
 9 int min( int a,  int b,  int c,  int d)
10 {
11     if(a > b)
12         a = b;
13     if(a > c)
14         a = c;
15     if(a > d)
16         a = d;
17     return a;
18 }
19 int dp[N][N];
20 int main()
21 {
22     freopen("in.txt","r",stdin);
23     int n,m,i,j,z,k;
24     char ch[2];
25     scanf("%d%d%s",&n,&m,str+1);
26     for(i=0; i<n; ++i)
27     {
28         scanf("%s",ch);
29         scanf("%d%d",&cost[ch[0]-'a'].add,&cost[ch[0]-'a'].del);
30     }
31     
32     for(z=2; z<=m; ++z)
33         for(i=1; i<=m-z+1; ++i)
34         {
35             j = i + z - 1;
36             if(str[i]==str[j])
37                 dp[i][j] = dp[i+1][j-1];
38             else
39                 dp[i][j] = min(dp[i+1][j] + cost[str[i]-'a'].add, dp[i+1][j] + cost[str[i]-'a'].del,
40                                 dp[i][j-1] + cost[str[j]-'a'].add, dp[i][j-1] + cost[str[j]-'a'].del);
41         }
42     printf("%d
",dp[1][m]);
43 }

View Code

poj1141 Brackets Sequence http://poj.org/problem?id=1141

dp[i][j] 表示将区间i--->j的括号变成regular sequence的最小花费.和上面的想法都差不多。

关键是记录路径。 path[i][j] == -1时，说明i+1--->j中没有任何括号和str[i]配对，所以你需要加入一个括号与str[i]配对，path[i][j] = k时，说明str[i] 与str[k]配对。

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 100 + 10;
 4 const int INF = 1 << 30;
 5 int dp[N][N];
 6 int path[N][N];
 7 char str[N];
 8 void print(int i, int j)
 9 {
10     if(i > j)
11         return ;
12     if(path[i][j] == -1)
13     {
14         if(str[i]=='(' || str[i]==')')
15             printf("()");
16         else
17             printf("[]");
18         print(i+1,j);
19     }
20     else
21     {
22         if(str[i]=='(' || str[i]==')')
23             printf("(");
24         else
25             printf("[");
26         print(i+1,path[i][j]-1);
27         if(str[i]=='(' || str[i]==')')
28             printf(")");
29         else
30             printf("]");
31         print(path[i][j]+1,j);
32     }
33 }
34 int main()
35 {
36     int n,i,j,k,z;
37     gets(str+1);
38     memset(path,-1,sizeof(path));
39     n = strlen(str+1);
40 
41     for(i=1; i<=n; ++i)
42         dp[i][i] = 1;
43     for(z=2; z<=n; z++)
44         for(i=1; i<=n-z+1; ++i)
45         {
46             j = z + i - 1;
47             dp[i][j] = dp[i+1][j] + 1;
48             path[i][j] = -1;
49             for(k=i+1; k<=j; ++k)
50             {
51                 if(str[i]=='(' &&str[k]==')' || str[i]=='['&&str[k]==']')
52                 if(dp[i][j] > dp[i+1][k-1] + dp[k+1][j])
53                 {
54                     dp[i][j] = dp[i+1][k-1] + dp[k+1][j];
55                     path[i][j] = k;
56                 }
57             }
58         }
59     print(1,n);
60     puts("");
61 }

View Code