本章面向区间动态规划展开
题目是从ACM训练内容上选用的，题面英文，内容较难
一本通上有几道区间dp的习题，模型比较类似，可以作为入门题

所谓区间问题，就是给出的问题是按区间的性质进行的，要么合并，要么分解为区间操作。《CCF中学生计算机程序设计》

区间DP的主要思想是先在小区间进行DP得到最优解，然后再利用小区间的最优解合并求大区间的最优解。《算法竞赛入门到进阶》

区间DP也属于线性DP中的一种，它以“区间长度”作为DP的“阶段”，使用两个坐标（区间的左、右端点）描述每个维度。在区间DP中，一个状态由若干个比它更小且包含于它的区间所代表的状态转移而来，因此，区间DP的决策往往就是划分区间的方法。区间DP的初态，一般由长度为1的“元区间”构成。这种向下划分、再向上递推的模式与某些树形结构，有很大的相似之处。《算法竞赛进阶指南》

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。

  1. 令状态 f[i, j] 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值，那么
  2. f[i, j] = max{f(i, k) + f(k + 1, j) + cost}
  1. Nested Ranges Style
  2.         (((a)(bc))(def))(ghijkl)
  4. Consecutive Ranges Style
  5.         (ab)(cde)(fg)
  7. General Ranges Style
  8.         回文串

Nested Ranges Style

例题，合并石子

在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。计算出将Ｎ堆石子合并成一堆的最小得分。
image.png
image.png
例题，【例9.18】合并石子

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int N = 310;
  7. int a[N], s[N], n;
  8. int f[N][N];  // f[i][j]表示合并[i,j]区间的石子需要耗费的体力
  10. int main(){
  11.     cin >> n;
  12.     for (int i = 1; i <= n; i++){
  13.         cin >> a[i];
  14.         s[i] = s[i - 1] + a[i];
  15.     }
  17.     memset(f, 0x3f, sizeof f);
  18.     for (int i = 1; i <= n; i++) f[i][i] = 0;   // 自己一个的时候，不用合并，耗费是0
  20.     for (int len = 2; len <= n; len++)          // 阶段，有两个石子才发生合并的行为
  21.         for (int i = 1; i <= n - len + 1; i++){ // 状态 左端点i
  22.             int j = i + len - 1;                // 状态 右端点j
  23.             for (int k = i; k < j; k++)
  24.                 f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
  25.             f[i][j] += s[j] - s[i - 1];
  26.         }
  28.     cout << f[1][n] << '\n';    
  30.     return 0;
  31. }

例题，CasketOfStar

image.png
image.png
image.png

  1. // my_code, cannot submit to Topcoder
  3. #include <bits/stdc++.h>
  5. using namespace std;
  7. const int N = 55;
  9. int weight[N], mem[N][N];
  10. int n;
  12. int best(int i, int j)
  13. {
  14.     if (j - i + 1 <= 2) return 0;
  15.     if (j - i + 1 == 3) return weight[i] * weight[j];
  17.     int &ret = mem[i][j];
  18.     if (ret != -1) return ret;
  20.     for (int k = i + 1; k < j; k++)
  21.         ret = max(ret, best(i, k) + best(k, j) + weight[i] * weight[j]);
  23.     return ret;
  24. }
  26. int main()
  27. {
  28.     cin >> n;
  29.     for (int i = 1; i <= n; i++) cin >> weight[i];
  31.     memset(mem, -1, sizeof mem);
  32.     cout << best(1, n) << '\n';
  34.     return 0;
  35. }

例题，Cutting Sticks

image.png

  1. // Cutting Sticks，请上机练习
  2. // 代码比较类似

例题，Optimal Array Multiplication Sequence

image.png

  1. // 难度：提高+/省选-
  2. // 需要递归输出方案
  3. // 请上机操作，课后自行展开，提高代码能力

Consecutive Ranges Style

例题，Pearls2a846e1562af749877f30ee62b0463f6 (1).jpg

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int N = 110, INF = 0x3f3f3f3f;
  7. int a[N], p[N], n, T;
  8. int mem[N][N];
  10. int best(int u, int last)
  11. {
  12.     if (u == n + 1) return 0;
  14.     int &ret = mem[u][last];
  15.     if (ret != INF) return ret;
  17.     int sum = 10;
  18.     for (int i = last; i <= u; i++) sum += a[i];
  20.     //buy now, add to right now interval
  21.     ret = min(ret, sum * p[u] + best(u + 1, u + 1));
  23.     if (u != n) ret = min(ret, best(u + 1, last));
  25.     return ret;
  26. }
  28. int main()
  29. {
  30.     cin >> T;
  31.     while (T--){
  32.         cin >> n;
  33.         for (int i = 1; i <= n; i++) cin >> a[i] >> p[i];
  35.         memset(mem, 0x3f, sizeof mem);
  36.         printf("%d\n", best(1, 1));
  37.     }
  39.     return 0;
  40. }
  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int N = 110, INF = 0x3f3f3f3f;
  7. int a[N], p[N], n, T;
  8. int mem[N][N];
  9. int s[N];
  11. int best(int u, int last)
  12. {
  13.     if (u == n + 1) return 0;
  15.     int &ret = mem[u][last];
  16.     if (ret != INF) return ret;
  18.     int sum = 10 + s[u] - s[last - 1];
  20.     //buy now, add to right now interval
  21.     ret = min(ret, sum * p[u] + best(u + 1, u + 1));
  23.     if (u != n) ret = min(ret, best(u + 1, last));
  25.     return ret;
  26. }
  28. int main()
  29. {
  30.     cin >> T;
  31.     while (T--){
  32.         cin >> n;
  33.         for (int i = 1; i <= n; i++) cin >> a[i] >> p[i];
  35.         memset(s, 0, sizeof s);
  36.         for (int i = 1; i <= n; i++) s[i] += s[i - 1] + a[i];
  38.         memset(mem, 0x3f, sizeof mem);
  39.         printf("%d\n", best(1, 1));
  40.     }
  42.     return 0;
  43. }
  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int N = 110, INF = 0x3f3f3f3f;
  7. int a[N], p[N], n, T, s[N];
  8. int dp[N];
  10. int main()
  11. {
  12.     cin >> T;
  13.     while (T--){
  14.         memset(s, 0, sizeof s);
  15.         memset(dp, 0x3f, sizeof dp);
  17.         cin >> n;
  18.         for (int i = 1; i <= n; i++) cin >> a[i] >> p[i];
  19.         for (int i = 1; i <= n; i++) s[i] += s[i - 1] + a[i];
  21.         dp[0] = 0;
  22.         for (int i = 1; i <= n; i++)
  23.             for (int j = 1; j <= i; j++)
  24.                 dp[i] = min(dp[i], dp[j - 1] + (s[i] - s[j - 1] + 10) * p[i]);
  26.         cout << dp[n] << '\n';
  27.     }
  29.     return 0;
  30. }

General Ranges Style

例题，String to Palindrome

image.png

  1. // 递归写法，my 10739_1.cpp
  3. # include<vector>
  4. # include<string>
  5. # include<iostream>
  6. using namespace std;
  7. string A, B;
  9. const int MAX  = 1000+9;
  11. int memo[MAX][MAX];
  13. int best(int i, int j)
  14. {
  15.     if(i >= j)
  16.         return 0;
  17.     int &ret = memo[i][j];
  18.     if(ret != -1)
  19.         return ret;
  21.     ret = best(i+1, j-1) + (A[i] != A[j]);
  22.     ret = min(ret, best(i+1, j)+1);
  23.     ret = min(ret, best(i, j-1)+1);
  25.     return ret;
  26. }
  29. int main() {
  31.     int num;
  32.     cin >> num;
  33.     for (int i = 1; i <= num; i++) {
  34.         cin >> A;
  36.         memset(memo, -1, sizeof memo);
  37.         cout << "Case " << i << ": " << best(0, (int)A.size()-1) << endl;
  38.     }
  40.     return 0;
  41. }
  1. // 循环写法
  3. #include<iostream>
  4. #include<string>
  5. using namespace std;
  7. int min(int a, int b, int c)
  8. {
  9.     if(b < a)        a = b;
  10.     if(c < a)        a = c;
  11.     return a;
  12. }
  14. int A[1001][1001]; /* The cost of substring A[i][j] */
  16. int main() 
  17. {
  18.     int i, j, k, len, cases, diag;
  19.     string str;
  21.     cin>>cases;
  22.     for (k = 1; k <= cases; k++)
  23.     {        
  24.         cin>>str;
  26.         for (i=0; i<str.size(); i++) /* Base case in diagonal */
  27.             A[i][i] = 0; /* Empty string */
  29.         for (len = 2; len <= str.size(); len++)    /* O(n^2) */
  30.         {    /* when len = 2 --> Special case */
  31.             for (i = 0; i+len<=str.size(); i++)
  32.             {
  33.                 j = i + len - 1, diag = 0;
  35.                 if (str[i] != str[j])
  36.                     diag = 1;
  38.                 if( i+1 <= j-1 ) /* at least j-i > 1 */
  39.                     A[i][j] = min(A[i+1][j]+1, A[i][j-1]+1, A[i+1][j-1]+diag);
  41.                 else    /* Undefined Stage (Not in base case) i = j+1 */
  42.                     A[i][j] = diag; /* j=i+1Tow char string */
  43.             }
  44.         }
  45.         cout<<"Case "<<k<<": "<<A[0][str.size()-1]<< "\n";
  46.     }
  47.     return 0;
  48. }
  51. // by zqiceberg
  53. #include <bits/stdc++.h>
  55. using namespace std;
  57. const int N = 1010;
  59. int T, idx;
  60. int dp[N][N];
  61. char s[N];
  63. int main()
  64. {
  65.     cin >> T;
  67.     while (T--){
  68.         scanf("%s", s);
  70.         int LEN = strlen(s);
  71.         for (int i = 0; i < LEN; i++) dp[i][i] = 0;
  73.         for (int len = 2; len <= LEN; len++)
  74.             for (int i = 0; i + len <= LEN; i++){
  75.                 int j = i + len - 1;
  76.                 int flag = 0;
  77.                 if (s[i] != s[j]) flag = 1;
  79.                 if (i + 1 <= j - 1){
  80.                     dp[i][j] = dp[i + 1][j - 1] + flag;
  81.                     dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1);
  82.                     dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
  83.                 }
  84.                 else dp[i][j] = flag;
  85.             }
  87.         printf("Case %d: %d\n", ++idx, dp[0][LEN - 1]);
  88.     }
  90.     return 0;
  91. }

例题，Cheapest Palindrome

  1. #include <iostream>
  2. #include <cstdio>
  4. using namespace std;
  6. const int N = 2010;
  8. char s[N];
  9. int w[N], dp[N][N];  // dp[i][j]表示 子区间[i...j]变成回文的最小花费
  10. int n, m;
  12. int main(){
  13.     cin >> n >> m;
  14.     scanf("%s", s);
  16.     for (int i = 0; i < n; i++){
  17.         char c;
  18.         int x, y;
  19.         cin >> c >> x >> y;
  20.         w[c - 'a'] = min(x, y);
  21.     }
  23.     // 枚举的区间是从小区间扩展到大区间
  24.     for (int i = m - 1; i >= 0; i--)
  25.         for (int j = i + 1; j < m; j++){
  26.             if (s[i] == s[j]){
  27.                 dp[i][j] = dp[i + 1][j - 1];
  28.             }
  29.             else{
  30.                 dp[i][j] = min(dp[i + 1][j] + w[s[i] - 'a'], 
  31.                         dp[i][j - 1] + w[s[j] - 'a']);
  32.             }
  33.         }
  35.     cout << dp[0][m - 1] << '\n';
  37.     return 0;
  38. }

例题，【例9.20】编辑距离

  1. //Tips: 对比一下最短编辑距离

例题代码

  1. // 例题，Cutting Sticks
  3. #include <bits/stdc++.h>
  5. using namespace std;
  7. const int N = 55;
  9. int a[N], l, n;
  10. int mem[N][N];
  12. int best(int i, int j)
  13. {
  14.     if (j - i <= 1) return 0;
  15.     if (j - i == 2) return a[j] - a[i];
  17.     int &ret = mem[i][j];
  18.     if (ret != 0x3f3f3f3f) return ret;
  20.     for (int k = i + 1; k < j; k++){
  21.         ret = min(ret, best(i, k) + best(k, j) + a[j] - a[i]);
  22.     }
  24.     return ret;
  25. }
  27. int main()
  28. {
  29.     while (cin >> l){
  30.         if (l == 0) break;
  32.         cin >> n;
  33.         for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  34.         a[0] = 0, a[n + 1] = l;
  35.         memset(mem, 0x3f, sizeof mem);
  36.         printf("The minimum cutting is %d.\n", best(0, n + 1));
  37.     }
  39.     return 0;
  40. }
  1. // 例题，Optimal Array Multiplication Sequence
  3. #include <bits/stdc++.h>
  5. using namespace std;
  7. typedef pair<int, int> PII;
  9. const int N = 20, INF = 0x3f3f3f3f;
  11. PII a[N];
  12. int path[N][N];
  13. int n, idx; 
  14. int mem[N][N];
  16. void print(int i, int j)
  17. {
  18.     if (j == i){
  19.         printf("A%d", i);
  20.         return ;
  21.     }
  23.     if (j - i == 1){
  24.         printf("(A%d x A%d)", i, j);
  25.         return ;
  26.     }
  28.     int k = path[i][j];
  29.     printf("(");
  30.     print(i, k); 
  31.     printf(" x ");
  32.     print(k + 1, j);
  33.     printf(")");
  34. }
  36. int best(int i, int j)
  37. {
  38.     if (j - i == 0) return 0;
  39.     if (j - i == 1) return mem[i][j] = a[i].first * a[i].second * a[j].second;
  41.     if (mem[i][j] != INF) return mem[i][j];
  43.     int &ret = mem[i][j];
  44.     for (int k = i; k < j; k++){
  45.         int t = best(i, k) + best(k + 1, j) + a[i].first * a[k].second * a[j].second;
  46.         if (t < ret){
  47.             ret = t;
  48.             path[i][j] = k;
  49.         }
  50.     }
  52.     return ret;
  53. }
  55. int main()
  56. {
  57.     while (cin >> n && n){
  58.         idx++;
  59.         for (int i = 1; i <= n; i++){
  60.             cin >> a[i].first >> a[i].second;
  61.         }
  63.         memset(mem, 0x3f, sizeof mem);
  64.         best(1, n);
  66.         printf("Case %d: ", idx);
  67.         print(1, n);
  68.         puts("");
  69.     }
  71.     return 0;
  72. }