区间DP（未完成）

lijingqian / 2023-09-01 / 原文

顾名思义，区间DP便是在区间上做DP ~~（废话）~~。区间DP的主要思想现在小区间上做DP得到最优解，通过把小区间的答案合并来得到大区间的最优解，最终得到整个区间的答案。

区间DP的计算量比较大。一个长度为 $n$ 的区间，编程时，区间DP至少需要两层 $for$ 循环，第1层的 $i$ 从区间的首部或尾部开始；第2层的 $j$ 从 $i$ 开始到 $n$ 结束，$i$ 和 $j$ 一起枚举所有的子区间。所以，区间DP的复杂度大于 $O(n^2)$ 一般为 $O(n^3)$。下面给出一道区间DP中的经典例题：石子合并。

石子合并：

有 $n$ 对石子排成一排，每堆石子有一定的数量。将 $n$ 对石子合并成一堆每次只能合并相邻的石子，合并的花费为这两堆石子的总数。经过 $n - 1$ 此合并后合成为一整堆，求最小总花费。
题目：luogu P1775

明显的，这道题不能用贪心算法求解，所以我们来用区间DP。

这里定义 $dp[i][j]$ 表示合并第 $i$ 堆到第 $j$ 堆石子的最小花费。

2.设计DP转移方程

在计算大区间 $[i, j]$ 的最小花费时，合并它的两个子区间 $[i, k]$ 和 $[k - 1, j]$，枚举所有可能的合并（$i \leqslant k < j$，即 $k$ 在 $i$ 至 $j$ 中滑动)。

状态转移方程即为：$dp[i][j] = min{dp[i][k] + dp[k + 1][j] + (s[j] - s[i - 1])}
其中 $s[i]$ 为从第 $1$ 堆到第 $i$ 堆石子的总数（前缀和）。

展示核心代码：

memset(dp, 0x3f, sizeof(dp));
for(int i = 1; i <= n; i++){
	dp[i][i] = 0;
}
for(int len = 2; len <= n; len++){  //len为区间[i, j]的长度
	for(int i = 1; i + len - 1 <= n; i++){
		int j = i + len - 1;
		for(int k = i; k < j; k++){
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + (s[j] - s[i - 1]));
		}
	}
}

输出即为 $dp[1][n]$。