区间 \(dp\) 通常解决的问题顺序有着很重要的作用，也就是说“前 \(i\) 个”的状态并不能很好地刻画出完整的状态
状态一般设计为 \(f[l][r]\)，表示 \(dp\) 完 \([l,r]\) 的区间的花费
后面经常补充状态，比如 \([0/1]\)，\([k]\) 来表示上一次取的是左/右端点，左右端点的状态，或者区间后面的一段情况，或者区间内数具有的性质
从中间转移
即每次扩展的是一个区间，用于解决合并类的问题
最典型的有石子合并
再补充一些题目：
发现同样是一个合并类问题，那么 \(f[i][j]=f[i][k]+1 (f[i][k]==f[k][j] )\)
\(f[l][r][0/1/2][0/1/2]\) 表示左右端点颜色分别为 \(0/1/2\) 的方案数
可以看左右端点是否是匹配括号，是则 \(dp\) \([l+1,r-1]\)，否则 \(dp\) \([l,k]\) 和 \([k+1,r]\)
这道题的一个启发点是对于这种括号匹配的问题，往往写成递归版的记忆化搜索会更好实现
\(f[l][r]=f[l+1][k-1]+f[k+1][r-1]+a[l]* a[k]* a[r]\)，表示 \(l,k,r\) 三个点形成了三角形并产生贡献
从两侧转移
POJ 3280 Cheapest Palindrome
题意：给你长度为m的字符串，其中有n种字符，每种字符都有两个值，分别是插入这个字符的代价，删除这个字符的代价，让你求将原先给出的那串字符变成一个回文串的最小代价。
这道题的思想还是很妙的
分情况讨论：
- 如果 \(l,r\) 相等，从 \(f[l+1,r-1]\) 转移
- 在前面插入 \(r\) 或后面删除 \(r\)，从 \(f[l,r-1]\) 转移
- 在后面插入 \(l\) 或前面删除 \(l\)，从 \(f[l+1,r]\) 转移
很妙的题，当时不以为然，AT 又出来发现不会
分两个数组 \(f,g\) 分别维护小明和小华取完后的状态
那么 \(f[l,r]=max(f[l+1,r]+a[l],f[l,r-1]+a[r])\)
\(g\) 的转移同理
古老的题了，设 \(f[l][r][0/1]\) 表示区间 \([l,r]\)，最后一次老王在左/右端点的最优值
维护后缀信息
设 \(f[l][r][s]\) 表示区间 \([l,r]\)，后面紧接着有 \(s\) 个与 \(r\) 相同的方块
这样的状态使得一种转移迎刃而解：即选取中间一个点 \(k\)，其中 \(k\) 与 \(r\) 颜色相同，砍掉 \([k+1,r-1]\) 的部分，让 \(r\) 以及后面的 \(s\) 个与 \(k\) 拼上
那么转移有两个：\(f[l][r][s]=f[l][r-1][0]+(s+a[r])^2\)
\(f[l][r][s]=f[l][k][a[r]+s]+f[k+1][r-1][0]\)
发现既然一次分发只和最值有关，那么只记录区间最值即可
设 \(g[l][r][mn][mx]\) 表示 \([l,r]\) 中最值分别为 \(mn\) 和 \(mx\) 的最优情况
设 \(f[l][r]\) 表示区间 \([l,r]\) 的最优解
那么 \(f[l][r]=min{g[l][r][a][b]+B*(b-a)^2+A}\)
考虑枚举断点 \(k\) 来转移 \(g\)
\(g[l][r][a][b]=min(f[l][k]+g[k+1][r][a][b],f[k+1][r]+g[l][k][a][b]+g[l][k][a][b]+g[k+1][r][a][b]\)
于是离散化后用 \(n^5\) 的优秀复杂度完成了此题
这是区间 \(dp\) 放到二维平面上的例子
设 \(f[l][r][i][j][k]\) 表示顶点为 \((l,r)\) 与 \((i,j)\) 的矩形分割了 \(k\) 次的最小值
每次只扩展横纵坐标之一
根据题目的限制，不能更改数据值，也就是说这棵 \(BST\) 的中序遍历是一定了，要做的是通过改变权值来旋转
设 \(f[l][r][s]\) 表示中序 \([l,r]\) 的节点，值 \(\ge s\) 的最小值
那么枚举一个树根 \(k\)，转移分情况讨论：
如果 \(k\) 的值大于等于 \(s\)，那么 \(f[l][r][s]=f[l][k-1][a[k].val]+f[k+1][j][a[k].val]+sum(i,j)\)
否则，\(f[l][r][s]=f[l][k-1][s]+f[k+1][r][s]+sum(i,j)+K\)
其意义在于这种消除的模式并不能贪心，其具有区间合并性
而 \(dp\) 状态相当于也是维护了后缀信息
详见 这里
- 资料
- 咕咕咕
区间 \(dp\) 与四边形不等式连接紧密，但是 \(noip\) 不考，还是下次学的时候再补吧