区间 dp
区间 dp 也分很多种，不过其实只是转移方式的不同罢了。
为了方便理解还是分开来写，应该不会写例题，会写类似泛化的东西。
合并类ψ(｀∇´)ψ
大概都是，某一个区间合并/处理完会得到一个代价，需要找到一种方式最优化代价。
状态一般设计为 \(dp(l, r)\) 表示 \([l, r]\) 处理完的代价，阶段是区间的长度（因为是考虑从小区间推到大区间）。
转移是 simple 的，枚举 \(l, r\)，枚举一个断点 \(k\)，考虑从 \(dp(l, k), dp(k + 1, r)\) 转移过来，并带上转移的代价，转移的代价是啥要具体问题具体考虑。
初始化的时候为了方便一般会直接计算 \(r - l + 1 = 1\) 的区间。
典型题目：Polygon，石子合并，能量项链。
石子合并的转移代价是 \(sum(l, r)\)，Polygon 是需要分最大最小值（因为有负数和乘法），能量项链是要维护头尾。
端点扩展类ψ(｀∇´)ψ
和合并类有点相似，不过一般来说偏向于“插入”和“覆盖”，换句话说区间端点的情况有可能会影响到答案。
状态仍然是 \(dp(l, r)\) 表示处理完 \((l, r)\) 的代价，有时候需要加上合并类的转移。
然后就是，考虑区间端点的情况，考虑扩展。
典型题目：合唱队，涂色，Cheapest Palindrome，关路灯。
涂色的比较经典一点，这个是对一个没有颜色的序列区间覆盖，然后要问达到对应序列的最小次数。
转移的时候就考虑枚举一个 \(k\)，假设 \([l, k], (k, r]\) 都达成了目标，合起来就行。
如果端点 \(s_l = s_r\)，考虑一下是不是可以有优化，注意到一个事情是，如果两个染色区间相交，实际上可以转化为两次存在包含关系的染色。
所以既然 \(s_l = s_r\)，说明我们可以把 \(l\) 的那一次染色扩展，其它染色不变，因为这里是覆盖，然后染色到 \(r\)，就不需要额外的一次操作了。
Cheapest Palindrome 要简单的多，设 \(dp(l, r)\) 表示让 \([l, r]\) 回文的最小操作次数。
时刻保持着我们在 dp 基础 里面提到的思想，我们需要认为，之前的都已经求出，只关心这个阶段。
所以因为里面都回文了，那么就只需要考虑 \(l, r\) 的情况，从 \(l - 1, r - 1\) 相关的情况转移过来就行。
这个可以分类讨论，篇幅原因在此省略。
合唱队则是要考虑插入，给定一个生成方式，给定一个最终序列，问有多少种插入顺序可以生成最终序列。
这里其实是计数 + 区间 dp，可以注意到一个固定的插入序列一定对应一个唯一的最终序列，所以天然不重不漏。
记 \(dp(l, r)\) 表示 \([l, r]\) 这段对应的插入序列的数量，但是你注意到人是可以从两边进去的。
所以要再记录一维 \(0/1\) 表示这一次插入的是从左边还是从右边插入的。
然后分两种情况转移从小区间就行。
关路灯则是注意到最优决策路径一定是一个不断变长的 S 形。
所以可以考虑每次在区间左右端点，下一次往哪边走，继续这个方向还是调头。
这种类似的题就都需要考虑到决策路径的情况才能想到区间 dp（）
分割类ψ(｀∇´)ψ
一般是给你一个序列，要求你把他分成 \(m\) 个部分，使得权值和最大。
这里的权值和会随着分割部分的不同而变化。
就有点类似线性 dp，设 \(dp(i, j)\) 表示前 \(i\) 个位置分了 \(j\) 个部分的最大权值。
然后枚举上一段端点就行了，方程一般是 \(dp(i, j) = \max\limits_{1 \le k < i}\{dp(k. j - 1) + w(k + 1, i)\}\)。
\(w\) 一般可以通过预处理得到。
典型题有邮局和花店橱窗布置。
一些想法
最近（May/05/2022）发现这个方程挺常见的（
而且还有很多变式，比如这东西实际上可以滚动数组，
\(i, j\) 分别作为阶段都是可以保证后效性的。
如果题目没有要求你具体要分多少段，可以省去第二维和 \(j\) 的枚举，并且 \(k\) 的取值范围将会变成 \(0 \le k < i\)。
很多数据结构优化 DP 题都会遇到这个方程(的变式)。
比如 The battle of chibi，The Bakery，Optimal Partition 都是。
任务安排1 也用了同样的思想。
第一题和第三、四题是没有要求分多少段，然后可以利用维护值域的树状数组代替平衡树插入决策，并以动态插入的方式保证方程的一个条件 \(j < i\) 成立。
第二题是要求了分多少段，我思考时为了统一优化方式，把 \(i,j\) 交换了，但事后发现其实两个都一样（
对这个方程的优化都是一个套路：固定外层循环，然后看内层循环决策集合的变化，根据不同情况选择数据结构进行维护。
而且数据结构起的作用都是快速地直接得到决策集合的转移信息（最值（线段树/树状数组），总和（树状数组））。
断环成链ψ(｀∇´)ψ
就是一个处理环上问题的小技巧，把链复制一倍，就可以决策到环上的所有情况了。
不过个人觉得这个叫“复制一倍，头尾相接”会比较好，比如最近有个 lct 题，是山区 \([l, r]\)，正常都是保留 \([l, r]\)，这不太好做。
于是就复制一倍，就可以变成保留 \([l, r]\) 了。