区间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
那么对于一个我们不知道答案的区间，计算他的答案有两个方面
①要求区间和
②要找到一种方法把自己分成两个区间
分成两个区间的时候，我们需要知道当前分成这两个区间之后的最大答案是多少。那么我们就枚举再哪里切断这个大区间让他变成两个小区间
于是就推得了状态转移方程。
那么对于最大的区间1—2*n， 首先我们可以知道如果他们只有两个的话那么是可以直接合并的， 而且还有一个条件可以确定，就是当区间中只有一个元素的时候，答案是0
那么对于一个我们不知道答案的区间，计算他的答案有两个方面
①要求区间和
②要找到一种方法把自己分成两个区间
分成两个区间的时候，我们需要知道当前分成这两个区间之后的最大答案是多少。那么我们就枚举再哪里切断这个大区间让他变成两个小区间
于是就推得了状态转移方程。
转载于:https://www.cnblogs.com/gc812/p/5777201.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/108904.html原文链接：https://javaforall.net
