区间dp笔记√

区间DP是一类在区间上进行dp的最优问题，一般是根据问题设出一个表示状态的dp，可以是二维的也可以是三维的，一般情况下为二维。

然后将问题划分成两个子问题，也就是一段区间分成左右两个区间，然后将左右两个区间合并到整个区间，或者说局部最优解合并为全局最优解，然后得解。

区间dp就是f[i][j]表示i到j的一段区间，然后去转移最优值的dp

一段区间表示一段状态，维护i~j的最优值来转移。

常见区间dp有：合并石子，破环成链类题目

其实对于环形区间DP有一个对付环的好方法:关于N取模（特殊处理0）！

e.g.能量项链

设 f[i,j]为第i到j颗珠子合并的最大能量为max{f[i,k]+f[k+1,j]+a[i]*a[k+1]+a[j+1]};//对k+1,j,j+1等数字关于m取模

这样一来，i>j时合并就是从i到n在回到1再到j
若使用复制一次数组的方法，时间复杂度为（2*n）^3,空间复杂度为4*n^2
环形取模方法与链式区间空间复杂度相同，且无空间浪费，时间复杂度为n^3

求和（e.g.石子合并）

对于求和的区间DP最重要的前缀和优化（要不然就要多花时间在求和上面）这种问题我们先考虑其中最大的区间1—2*n （因为是绕成一圈所以是2*n，2*n的话可以保证在一个环上所有的区间情况）。

那么对于最大的区间1—2*n，首先我们可以知道如果他们只有两个的话那么是可以直接合并的，而且还有一个条件可以确定，就是当区间中只有一个元素的时候，答案是0

那么对于一个我们不知道答案的区间，计算他的答案有两个方面

①要求区间和

②要找到一种方法把自己分成两个区间

分成两个区间的时候，我们需要知道当前分成这两个区间之后的最大答案是多少。那么我们就枚举再哪里切断这个大区间让他变成两个小区间

于是就推得了状态转移方程。

转载于:https://www.cnblogs.com/gc812/p/5777201.html

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/108904.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权正版激活】： 官方授权正版激活支持Jetbrains家族下所有IDE 使用个人JB账号...