区间DP

• 是一类子问题从短到长，而不是从左到右的动态规划问题。

状态

一般是：$dp_{i,j}$ 表示将区间 $[i,j]$ 的元素合并、拆分的最值、方案数。

转移

for (int len = 2; len <= n; len++)//这问题
	for (int i = 1; i + len - 1 <= n; i++)//状态
	{
		int j = i + len - 1;
		for (int k = i; k < j; k++)//决策点
		dp[i][j] = 运算(dp[i][j], 状态转移方程);
	}

例题

洛谷P1775

P1775 石子合并（弱化版）

设有 $N(N \le 300)$ 堆石子排成一排，其编号为 $1,2,3,\cdots,N$。每堆石子有一定的质量 $m_i\ (m_i \le 1000)$。现在要将这 $N$ 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。

状态

$dp_{i,j}$ 表示将区间 $[i,j]$ 的元素合并的最小代价。

转移

for (int k = i; k < j; k++)
	dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
dp[i][j] += sum[j] - sum[i - 1];

答案

$dp_{1,n}$

洛谷P3146

P3146 [USACO16OPEN] 248 G

贝西喜欢在手机上下载游戏来玩，尽管她确实觉得对于自己巨大的蹄子来说，小小的触摸屏用起来相当笨拙。

她对当前正在玩的这个游戏特别感兴趣。游戏开始时给定一个包含 $N$ 个正整数的序列（$2 \leq N \leq 248$），每个数的范围在 $1 \ldots 40$ 之间。在一次操作中，贝西可以选择两个相邻且相等的数，将它们替换为一个比原数大 1 的数（例如，她可以将两个相邻的 7 替换为一个 8）。游戏的目标是最大化最终序列中的最大数值。请帮助贝西获得尽可能高的分数！

状态

$dp_{i,j}$ 表示将区间 $[i,j]$ 的元素合并的最大能得到的数。

转移

for (int k = i; k < j; k++)
	if (dp[i][k] == dp[k + 1][j])
		dp[i][j] = max(dp[i][j], dp[i][k] + 1);

答案

$max(dp_{i,j})$

洛谷P1622

P1622 释放囚犯

Caima 王国中有一个奇怪的监狱，这个监狱一共有 $P$ 个牢房，这些牢房一字排开，第 $i$ 个紧挨着第 $i+1$ 个（最后一个除外）。现在正好牢房是满的。

上级下发了一个释放名单，要求每天释放名单上的一个人。这可把看守们吓得不轻，因为看守们知道，现在牢房中的 $P$ 个人，可以相互之间传话。如果某个人离开了，那么原来和这个人能说上话的人，都会很气愤，导致他们那天会一直大吼大叫，搞得看守很头疼。如果给这些要发火的人吃上肉，他们就会安静点。

状态

$dp_{i,j}$ 表示将区间 $[a_i,a_j]$ 的人放在一起需要给的肉的数量。

转移

for (int k = i; k < j; k++)
	dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
dp[i][j] += sum[j] - sum[i - 1] + j - i - 1;

答案

$dp_{1,n}$

洛谷P2890

P2890 [USACO07OPEN] Cheapest Palindrome G

给定一个由 $n$ 个不同的小写字母构成的长 $m$ 的字符串 $s$。可以通过在 $s$ 的任意位置增减字母将 $s$ 改为回文串。增减字母的花费不同，求最小花费。

状态

$dp_{i,j}$ 表示将区间 $[i,j]$ 变成回文串的最小花费。

转移

if (s[i] == s[j])
	dp[i][j] = (len > 2 ? dp[i + 1][j - 1] : 0);
dp[i][j] = min({ dp[i][j],dp[i][j - 1] + a[s[j]],dp[i + 1][j] + a[s[i]] });

答案

$dp_{1,n}$

类似题

• P1435 [IOI 2000] 回文字串，只不过代价为 $1$。

洛谷P2858

P2858 [USACO06FEB] Treats for the Cows G/S

约翰经常给产奶量高的奶牛发特殊津贴，于是很快奶牛们拥有了大笔不知该怎么花的钱。为此，约翰购置了 $N$（$1 \leq N \leq 2000$） 份美味的零食来卖给奶牛们。每天约翰售出一份零食。当然约翰希望这些零食全部售出后能得到最大的收益，这些零食有以下这些有趣的特性：

• 零食按照 $1, \ldots, N$ 编号，它们被排成一列放在一个很长的盒子里。盒子的两端都有开口，约翰每天可以从盒子的任一端取出最外面的一个。
• 与美酒与好吃的奶酪相似，这些零食储存得越久就越好吃。当然，这样约翰就可以把它们卖出更高的价钱。
• 每份零食的初始价值不一定相同。约翰进货时，第i份零食的初始价值为 $V_i$（$1 \leq V \leq 1000$）。
• 第i份零食如果在被买进后的第 $a$ 天出售，则它的售价是 $V_i \times a$。

$V_i$ 的是从盒子顶端往下的第i份零食的初始价值。约翰告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱。

状态

$dp_{i,j}$ 表示只将区间 $[a_i,a_j]$ 买完的最大价值。

转移

dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) + sum[j] - sum[i - 1];

答案

$dp_{1,n}$

洛谷P4170

P4170 [CQOI2007] 涂色

状态

$dp_{i,j}$ 表示将区间 $[i,j]$ 达到目标的最少涂色次数。

转移

if (s[i] == s[j])
	dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]);
else
	for (int k = i; k < j; k++)
		dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);

答案

$dp_{1,n}$

洛谷P3205

P3205 [HNOI2010] 合唱队

…
小 A 心中有一个理想队形，他想知道多少种初始队形可以获得理想的队形。
请求出答案对 $19650827$ 取模的值。

状态

$dp_{i,j,0/1}$ 表示这一次是添加到开头/结尾，将区间 $[i,j]$ 达到理想的队形的方案数。

转移

if (a[i] < a[i + 1])
	dp[i][j][0] = (dp[i][j][0] + dp[i + 1][j][0]) % mod;
if (a[i] < a[j])
	dp[i][j][0] = (dp[i][j][0] + dp[i + 1][j][1]) % mod;
if (a[j] > a[j - 1])
	dp[i][j][1] = (dp[i][j][1] + dp[i][j - 1][1]) % mod;
if (a[j] > a[i])
	dp[i][j][1] = (dp[i][j][1] + dp[i][j - 1][0]) % mod;

答案

$(dp_{1,n,0}+dp_{1,n,1})\mod 19650827$

总结

1. 题目特征上有合并类、拆分类、两端处理类；
2. 求最值类区间DP，需要注意无效状态初始化；
3. 输出答案前，判断是否需要枚举；
4. 决策点一般是在中间枚举或是两个端点；
5. 若转移时可以从 $dp_{i+1,j-1}$ 递推，需要注意 $len=2$ 的情况；
6. 初始状态要分析清楚。