总结：区间 DP

Cartis · 2025-04-02 12:47:23 · 算法·理论

区间 DP

区间 DP 是 DP 的一种，主要处理有关于区间的动态规划问题，需要注意的是，区间 DP 主要处理的是一类子问题从短到长，而不是从左到右或者是从右到左（这就属于线性 DP 了）。

DP 三要素

1. 状态定义：

   对于一般的区间 DP 问题，我们只需要一个二维的 DP 数组即可，我们定义 f_{i,j} 表示将区间 [i,j] 之间的元素或者是数字合并 / 拆分 /…… 等操作的最大值或最小值或者是方案数。

2. 状态转移：

   状态转移其实非常好理解，我们用一个伪代码来表示出来，其实一般的区间 DP 都有两种不同的转移方式，这两种转移方式的时间复杂度也是不同的。

   • 常用的模板：

     for (int l = 2; l <= n; l++) // 这里是以 l 作为长度来枚举子问题
     for (int i = 1; i + l - 1 <= n; i++) // 枚举状态
     int j = i + l - 1; // 处理的区间 [i, j]
     for (int k = i; k < j; k++)
      f[i][j] = (min / max / cnt)(f[i][j], 状态转移方程)   

3. 最终答案：

   区间 DP 由于是处理一类区间的问题，所以我们的答案一般是不固定的，所以答案有非常多的可能性，例如 f_{1,n} 或者是 \max(f_{i,j})，都有可能。

然后我们就将区间 DP 的思想讲解完了，接下来我们来讲解例题。

例题

• P1775 石子合并（弱化版）

这是一道非常模板的区间 DP 题，我们来思考一下，每次以合并，我们可以在从中切一刀，分成两半，就假设合并这两半，然后合并的价值其实就是 f[i][k] + f[k + 1][j] + s[j] - s[i - 1]，之所以还要加上前缀和数组 s，是因为这一次的合并也是需要价值的，最终的答案就是 f_{1,n}。

代码：

// Code by __HJC__
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 300 + 5, kInf = 1e9 + 10;

int n, m[kMaxN], f[kMaxN][kMaxN], s[kMaxN];

int main() {
  cin >> n;
  fill(f[1], f[n + 1], kInf);
  for (int i = 1; i <= n; i++) {
    cin >> m[i];
    s[i] = s[i - 1] + m[i], f[i][i] = 0;
  }
  for (int l = 2; l <= n; l++) {
    for (int i = 1; i + l - 1 <= n; i++) {
      int j = i + l - 1;
      for (int k = i; k < j; k++) {
        f[i][j] = min(f[i][k] + f[k + 1][j] + s[j] - s[i - 1], f[i][j]);
      }
    }
  }
  cout << f[1][n];
  return 0;
}

• P3146 [USACO16OPEN] 248 G

其实也是和上面那一道模板其实是一样的，这里只需要限制一下可以转移限制即可，因为题目要求的是只有相同的才可以进行转移，所以我们只需要特殊判断一下 DP 数组当前的是否相同，然后直接进行转移即可。

需要注意的是，这道题中输出的答案并不是 f_{1,n}，而是所以 f 的最大值，因为不一定每次玩到最终，所以我们需要取最大值。

代码：

// Code by __HJC__
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 248 + 5, kInf = -1e9 - 10;

int n, a[kMaxN], f[kMaxN][kMaxN], ans;

int main() {
  cin >> n;
  fill(f[1], f[n + 1], kInf);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    f[i][i] = a[i], ans = max(ans, a[i]);
  }
  for (int l = 2; l <= n; l++) {
    for (int i = 1; i + l - 1 <= n; i++) {
      int j = i + l - 1;
      for (int k = i; k < j; k++) {
        if (f[i][k] == f[k + 1][j]) {
          f[i][j] = max(f[i][j], f[i][k] + 1);
          ans = max(ans, f[i][j]);
        }
      }
    }
  }
  cout << ans;
  return 0;
}

• P1622 释放囚犯

其实就是区间 DP 模板题目的改版，我们其实可以把 q 个人被释放，看作为将 q 个人加入进来，这样子就非常好理解了，每次加入进来，旁边的人会因为有人可以说话了，就会需要吃肉，所以，每次都可以加上旁边两个联通块内的数量总数，就相当于了区间 DP 中的合并操作，所以我们预处理完前缀和之类的一开始的一些必要条件，就可以直接使用类似石子合并的区间 DP 代码通过这道题目了。

图片理解：

代码：

// Code by __HJC__
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1000 + 5, kInf = 1e9 + 10;

int p, q, id[kMaxN], k[kMaxN], f[kMaxN][kMaxN], s[kMaxN];

int main() {
  cin >> p >> q;
  for (int i = 1; i <= q; i++) {
    cin >> id[i];
  }
  id[++q] = p + 1;
  fill(f[0], f[q + 1], kInf);
  for (int i = 1; i <= q; i++) {
    s[i] = s[i - 1] + id[i] - id[i - 1] - 1;
    f[i][i] = 0;
  }
  for (int l = 2; l <= q; l++) {
    for (int i = 1; i + l - 1 <= q; i++) {
      int j = i + l - 1;
      for (int k = i; k < j; k++) {
        f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + j - i - 1 + s[j] - s[i - 1]);
      }
    }
  }
  cout << f[1][q];
  return 0;
}

• P2890 [USACO07OPEN] Cheapest Palindrome G

这道题就是属于 O(1) 进行转移类的区间 DP，所以我们需要改一下转移方式，可以发现，转移出状态 f_{i,j}，其实只需要从 f_{i+1,j}，f_{i,j-1}，或者是 f_{i+1,j-1}，其中，从 f_{i+1,j-1} 转移过来的条件其实是 s_{i} = s_{j}，因为如果等于，那么就不需要新增一个字符或者删除一个字符，因为它本身就已经是一个回文串了，但是其他两种，无非是在左或右边分别补全一个字符使得变成回文串，所以添加与减少都无所谓，只需要取最小值即可。

代码：

// Code by __HJC__
#include <bits/stdc++.h>

using namespace std;
using Pii = pair<int, int>;

const int kMaxN = 2000 + 5, kMaxC = 27, kInf = 1e9 + 10;

int n, m, f[kMaxN][kMaxN], v[kMaxC];
string s;
Pii c[kMaxC];

int main() {
  cin >> n >> m >> s;
  s = "#" + s;
  fill(f[0], f[m + 1], kInf);
  for (char ch; n--;) {
    cin >> ch >> c[ch - 'a'].first >> c[ch - 'a'].second;
    v[ch - 'a'] = min(c[ch - 'a'].first, c[ch - 'a'].second);
  }
  for (int i = 1; i <= m; i++) {
    f[i][i] = 0;
  }
  for (int l = 2; l <= m; l++) {
    for (int i = 1; i + l - 1 <= m; i++) {
      int j = i + l - 1;
      if (s[i] == s[j]) {
        f[i][j] = l > 2 ? min(f[i][j], f[i + 1][j - 1]) : 0;
      }
      f[i][j] = min(f[i][j], min(f[i + 1][j] + v[s[i] - 'a'], f[i][j - 1] + v[s[j] - 'a']));
    }
  }
  cout << f[1][m] << '\n';
  return 0;
}

• P2858 [USACO06FEB] Treats for the Cows G/S

其实这道题的转移和上面一道题目基本一样，只是需要注意 f_{i,i} 在进行初始化时需要初始化为 v_i \times n，因为到第 n 天卖出肯定是最优的。

代码：

// Code by __HJC__
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 2000 + 5, kInf = -1e9;

int n, v[kMaxN], f[kMaxN][kMaxN], s[kMaxN];

int main() {
  cin >> n;
  fill(f[0], f[n + 1], kInf);
  for (int i = 1; i <= n; i++) {
    cin >> v[i];
    f[i][i] = v[i] * n;
  }
  for (int l = 2; l <= n; l++) {
    for (int i = 1; i + l - 1 <= n; i++) {
      int j = i + l - 1;
      f[i][j] = max(f[i + 1][j] + (i - 1 + n - j + 1) * v[i], f[i][j - 1] + (i - 1 + n - j + 1) * v[j]);
    }
  }
  cout << f[1][n];
  return 0;
}

• P4170 [CQOI2007] 涂色

这道题是为数不多的一道需要考虑两种转移的题目，我们其实可以分两种情况讨论。

1. 那么我们就可以将区间 $[i, j]$ 染成 $s_{i}$，然后从 $f_{i+1,j-1}$ 进行转移过来.
2. s_i \neq s_j

   那么我们就可以直接枚举中间断点 k 来进行转移操作。

代码：

// Code by __HJC__
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 2e3 + 5, kInf = 1e9 + 10;

int n, f[kMaxN][kMaxN];
string s;

int main() {
  cin >> s;
  n = s.size();
  s = "#" + s;
  fill(f[0], f[n + 1], kInf);
  for (int i = 1; i <= n; i++) {
    f[i][i] = 1;
  }
  for (int l = 2; l <= n; l++) {
    for (int i = 1; i + l - 1 <= n; i++) {
      int j = i + l - 1;
      f[i][j] = s[i] == s[j] ? min(f[i + 1][j], f[i][j - 1]) : f[i][j];
      for (int k = i; k < j; k++) {
        f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
      }
    }
  }
  cout << f[1][n] << '\n';
  return 0;
}

• P3205 [HNOI2010] 合唱队

这道题有一些不同，因为我们如果直接进行两端的转移，那么有一个条件我们是不知道的，就是当前这个人到底是从左边进入的，还是从右边进入的呢？这是无法解决的，所以 DP 常用套路启动，那就是描述不够就加维度，我们在加上一个维度用来维护是从左边进入的还是从右边进入的，然后直接进行转移即可。

注意需要开 long long 和需要进行取模操作。

代码：

// Code by __HJC__
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int kMaxN = 1000 + 5, kMod = 19650827;

int n, f[kMaxN][kMaxN][2], h[kMaxN];

signed main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
    f[i][i][0] = 1;
  }
  for (int l = 2; l <= n; l++) {
    for (int i = 1; i + l - 1 <= n; i++) {
      int j = i + l - 1;
      if (h[i] < h[i + 1]) {
        f[i][j][0] += f[i + 1][j][0];
      }
      if (h[i] < h[j]) {
        f[i][j][0] += f[i + 1][j][1];
      }
      if (h[j] > h[j - 1]) {
        f[i][j][1] += f[i][j - 1][1];
      }
      if (h[j] > h[i]) {
        f[i][j][1] += f[i][j - 1][0];
      }
      f[i][j][0] %= kMod, f[i][j][1] %= kMod;
    }
  }
  cout << (f[1][n][0] + f[1][n][1]) % kMod;
  return 0;
}

• P1435 [IOI 2000] 回文字串

和上面拿到回文串的题目一摸一样，只是没有了权重，所以直接模板转移即可。

// Code by __HJC__
#include <bits/stdc++.h>

using namespace std;

const int kMaxL = 1000 + 5, kInf = 1e9 + 10;

int n, f[kMaxL][kMaxL];
string s;

int main() {
  cin >> s;
  n = s.size(), s = "#" + s;
  for (int l = 2; l <= n; l++) {
    for (int i = 1; i + l - 1 <= n; i++) {
      int j = i + l - 1;
      if (s[i] == s[j]) {
        f[i][j] = l <= 2 ? 0 : f[i + 1][j - 1];
      } else {
        f[i][j] = min(f[i + 1][j] + 1, f[i][j - 1] + 1);
      }
    }
  }
  cout << f[1][n] << '\n';
  return 0;
}