区间DP-526互联

一.定义
即对于一个区间进行的dp
二.经典转移方程
1.枚举断点型
f[l][r]=min(f[l][k-1],f[k][r]) (l+1<=k<=r)
2.左右端点型
f[l][r]=min(f[l][r-1],f[l+1][r])
3.有一定条件型
f[l][r][k]=f[l][r-1][k-1]+f[r][r][0]
三.主要思想
1.遇到环时，破环为链，转化为区间求解
2.区间由短到长更新，最终将整体1~n的答案求解出来
3.其n范围一般很小，因为其时间复杂度一般为n^3
4.有时从序列中删数的操作倒过来想，转化为将数插入序列中，会简单一些
5.通常要分类讨论，每种情况会对应上面的不同的转移方程