区间DP

引入

• 给定一堆长度为 $n$ 的石子，每个石子有其重量 $a_i$ ,你需要做的是不断的合并相邻石子，每次合并$i,j$两堆石子需要付出 $a_i+a_j$的代价，你必须不断合并直到所有石子均被合并完成。你需要知道你付出的最小代价是多少

特点

• 区间dp的特点我们一般认为有以下
  • 在某一个序列上的一个区间进行操作,如(合并)
  • 可以利用子区间的最优解来构造全局的最优解

dp含义以及状态转移

状态定义：

• 区间状态，我们定义$dp[i][j]$表示从位置 $i$ 到位置 $j$ 的最优解(最小代价，最大收益等)
• 对于每一个 $dp[i][j]$ 我们都应该保证其状态能从子区间转移而来

状态转移：

• 区间划分：为了计算$dp[i][j]$,我们往往需要一个中间值 $k\in [i,j)$
  • $k$将区间$[i,j]$划分为两个区间 $[i,k]$ 和 $[k+1,j]$
  • 我们通过合并这两个子区间的代价来进行选择
  • 为了能够知道所有状态的最优解,$k$应该遍历$[i,j)$
• 递推式

$$dp[i][j]=\underset{i\le k<j}{\min }\{dp[i][k]+dp[k+1][i]+\mathrm{cost}(i,k,j)\}$$

• 其中 $\mathrm{cost}(i,j,k)$ 为合并两个子区间所产生的代价

dp计算思路

• 一般区间dp有三层for循环，第一层枚举长度 $len$ ,第二次找区间起始点 $i$ ，第三层遍历所有中间点 $k$

Tip

区间dp的复杂度为 $O(n^3)$

一般模板代码

我们以引入问题为例进行分析

vector<vector<int>> dp(N,vector<int>(N));
// 我们认为序列长度有n
for(int i = 1 ; i <= n ; i++)｛
	dp[i][i] = 0;
｝
// 预处理,根据题目含义做出预处理数组(前缀和，或合并代价)(此处为合并石子，即石子的前缀和，用于计算区间代价)
vector<int> vv(N);
for(int i = 1; i <= n; i++) {
	vv[i] = vv[i-1] + v[i];
}
 
//进行区间dp，枚举所有长度n
for(int len = 2;len <= n; len++){            //第一层，枚举长度
	for(int i = 1; i + len - 1 <= n; i++){   //第二层，枚举起点
		int j = i + len - 1;                 //计算终点
		dp[i][j] = INT_MAX;                 
		for(int k = i; k < j ;k++{
			dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j] + (vv[j] - vv[i-1]);       // 区间dp转移，遍历所有中间节点，取最小值
		}
	}
}
 
cout << dp[1][n];         //答案即为从1-n的区间最优解