区间dp

顾名思义，就是在区间上进行dp。

区间DP用于解决决策涉及到相邻区间合并的问题。

它的转移方向是由小区间向大区间转移，所以在转移的时候，要注意转移顺序。

经典例题一发

P1880 [NOI1995] 石子合并

先来看状态转移方程： $$ dp[i][j]=max(dp[i][k]+dp[k+1][j])+\sum^j_inum[i] $$ $dp[i][j]$ 表示以 $i$ 为起点，$j$ 为终点的区间合并成一堆所取到的最大。因为无论如何合并，本次合并所付出的代价相同，均为 $\sum^j_inum[i]$。

所以，我们只需要考虑如何搞才能让合并前的两堆的代价之和最大即可。

方法就是遍历中间点 $k$，表示两堆的分割点，也就遍历了所有可能的合并情况，从中取最优，这也正是区间dp的精华所在。

我们发现，跑完之后的dp数组中成三角形，这也正是区间dp区别于线性dp最显而易见的地方。

环

很多时候，题目中会给出“……连成一个环”。

这似乎，又是一个很难很难的问题……

不，聪明的人类总是有流氓的做法。

其实，就是把原来的数组在结尾在拼接一个一样的，但是最长的区间长度不变即可。(注意遍历时区间起止点的坐标范围和 $+1$ 问题)

几道题

莫得办法，dp这玩意只能用题去体会。