本文共 3618 字，大约阅读时间需要 12 分钟。

通过前一阵对动态规划的学习，动态规划就是子问题之间的关系，然后所有状态里找最优，即一个问题的最优解只取决于其子问题的最优解，其他的不是最优的解对问题并没有影响。

这一周学的是区间dp，和线性dp大同小异

同样都是每次考虑i到j这一区段的问题，但区别是线性dp在数轴上只关注一个点，而区间dp是考虑一组点，即一个区间，把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可，本质都是通过求子问题来逐步达到最后的结果。

区间dp的最大特点是循环，根据下标做循环，把所有子问题的解先求出来，看到问题想方程

套路居多，这周特意挑了同一个套路的题做，不过内含机理也只是简单的理解一丝丝，大部分还是套用，利用之前做过的题来修改方程和细节，罪过

for(int len=2; len<=n; len++){//长度

for(int i=1,j = i+len-1; j<=n; i++,j++){//i为起点，j为终点

for(int k=1; k<=len; k++){//分割点，把这一小区间分割成两个区间，dp[i][k]+dp[k+1][j]

d[i][j] =//状态转移方程

} } }

一直用dp[i][j]来标记从i到j的要求，长度从1或者2开始列起（每一子段），求解这一段的最优解，然后用循环一直增大长度，直到从开头到末尾。

对于不同的问题我们只需要考虑一下dp数组的初始化和状态转移方程即可 还有一个小规律，当我们需要求解最大值时，通常会提前让转移数组提前赋值为0,当我们需要求解最小值时，提前赋一个超大值。

1.石子问题（数字相加合并）（前缀和）

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 直线型:（一排） 我们需要提前处理，这个题利用前缀和公式，一维：sum[i]=sum[i-1]+a[i]; sum[i][j]表示第i到第j堆石子的总数量。又因为要分别输出最大值和最小值，所以我们用两个转移数组来标记。 当我们进行3个长度的合并时，则有2种合并方案：1号、2号、3号合并或者2号、3号、4号合并。在1号、2号、3号合并的过程中，则又有两种方案：{ {1,2},3} 还是 {1,{2,3}}。举例第一种情况，花费代价是 sum[1][3] = sum[1][2] + sum[3][3] ，但是因为计算sum[1][2]的时候也花费了一些代价，然后再加上第一步已经花费的代价 sum[1][2]，所以总代价为 dp[1][3] = sum[1][2] + sum[1][3] 最后总结出一个转移方程 最小值：d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]+sum[j]-sum[i-1]); 最大值：d[i][j]=max(d[i][j],d[i][k]+d[k+1][j]+sum[j]-sum[i-1]); 圆形型：（首尾相接） 由直线型可以知道，我们求的是第一个到第n个合并后的结果，当成为圆形之后，我们的起点就有了n种情况，所以结果会与我们的套路有一点点不同，就需要一个for循环来找我们想要的答案。这就将圆形有转换回了直线型的，还是原来的做法，再将赋初始值的步骤多加一遍，赋2n个即可其他步骤均相同。

再说一个同样是圆形的题

2.星球上的能量项链（取个起点依次，三位数相乘）（easy） 给一串珠子的能量，可以用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。设N=4，4颗珠子的能量依次为(2，3) (3，5) (5，10) (10，2)，上一个的首和下一个的尾相同，且合并后头变为上一个的头，尾变成下一个的尾，请你设计一个聚合顺序，使一串项链释放出的总能量最大。 由题可知，跟石头的首位相接是一样的，最后是组成了一个圆形，所以总共是2n个了，这个题因为是选定一个点后顺时针进行计算即可，所以和石子合并相比不需要提前求出什么能量，只是转移方程的条件改变了，别忘了圆圈系列的标配，输出的时候要用一个数组来循环。 转移方程： d[i][j]=max(d[i][j],d[i][k]+d[k][j]+a[i]*a[j]*a[k])； 3.舞会换衣服+括号匹配（判断是否相等） 有N个宴会，对于每一个宴会，女猪脚都要穿一种礼服，礼服可以套着穿，但是脱了的不能再用，参加宴会必须按顺序来，从第一个到第N个，问参加这些宴会最少需要几件礼服？ 还是石子的合并思想，只不过这个题又去掉了能量，问的是数量问题，还是从只有两天算起，我们需要判断的是第二天和第一天是否相同，相同的话第二天的件数就等于第一天的即可，当有三天时，我们就要分别判断第三天是否和第一天相同，如果相同，第三天的件数就等于第二天的即可，如果不相同的话，就要判断是否和第二天相同，推广一下就是找前面的小区间是否有与这一天相同的

和换衣服问题类似的相等问题，求匹配的个数，仍然是判断相等的话就是上一种情况加2，不相等的话再去找区间的最优情况，值得注意的是，这里的上一种情况的表示方法是： d[i][j]=d[i+1][j-1]+2，因为是两边同时决定的。

贴个代码，这个题有些许不同

for(int len=2; len<=n; len++)        {            for(int i=1,j=len+i-1; j<=n; j++,i++)            {                d[i][j]=mann;                if(a[i]==a[j])  d[i][j]=d[i][j-1];//当开头和结尾相同的时候，显然不用再穿了，直接取上一个情况                for(int k=i; k

4.回文序列（同是判断相等问题）

回文序列是插入或者删除一个字符都需要一定的代价，问怎样可以使这个字符串变成一个回文串，且花费最小。 这个题只有四种情况，头部删除，头部添加，尾部删除，尾部添加 这个题值得关注的的特殊点在于，增删字符的花费不同，但事实上我们可以直接取增加或者删除的最小值，反正后面也要取最优 所以在一开始我们就直接记录每个字母的花费即可，a[int©]=min(x,y); 其余地方就跟上面的判断相等问题一样了，如果这一串的开头和结尾相同，咱就取上一个值， d[i][j]=d[i+1][j-1]（和括号一样的） 还是有点不同的，再贴个代码

for(int len=2; len<=m; len++)    {        for(int i=0,j=len+i-1; j

前缀和

这里补充一个前缀和，前缀和是一种重要的预处理，能大大降低查询的时间复杂度，是dp的一种处理方法，也是需要转移方程。

一维前缀和

方程：sum[i] = sum[i-1] + a[i]   其实可以把它理解为数学上的一维数列的前n项和，即前n项相加的和   S[i] = ∑A[j] ( j ∈ [1,i]）    通常我们会求解某一区段的和，直接拿来使用即可，sum [r]-sum[l] 上面说过的Q题和O题(石子问题)，就用了前缀和的方法，提前求出前n项和。    二维前缀和

求前缀和的方程：

sum[x][y]=sum[x-1][y]+sum[x][y-1]-sum[x-1][y-1]+a[x][y] 最经典的题是，最大子矩阵和，给定一个n* m大小的矩阵a，求以(x1,y1)为左上角坐标和(x2,y2)为右下角坐标的子矩阵的所有元素和。 先是求前缀和，即整个S, S=S2+S3-S1+a[x][y] (S1是交叉部分) 我们最终要求解的是S4的面积，而它的面积等于S-S2-S3+S1，其中S1,S2,S3已经用前缀和求出来了。 最后的答案公式:   s[i][j]+=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]。    前一阵cf做题就有一个利用前缀和的，这就是dp题中一种做题方法，跟经典的求最大子矩阵和很相似。   给一个n行m列的由.和* 组成的二维数组，横着的两个或者竖着的两个"."都符合条件，再给q对点（左上角和右下角）之间的矩形，然后问询问区间内符合条件的两连点有多少个。这里不详细说题解了，简直一毛一样，只是子矩阵换成了1×2和2×1的矩阵而已。

小小心得

可能是喜欢模板的原因，感觉区间比线性好做，虽然这也都不是我独立做出来的，大部分还是参考别人的，但是这个周收获还挺多，起码对动态规划又对了点了解，这周做的题也只是区间dp的冰山一角，其他类型的等我总结出来再说，想要一开始就彻底整明白不太容易，多做点题会更便于了解，做题多多，好处多多

嘚儿驾~