复习

线性dp

8.14

8.19

背包

8.20

1. 01背包 倒序（循环顺序：物品-费用）
2. 完全背包 正序
3. 多重背包 二进制拆分
4. 二维费用背包 加限制条件（eg：加一维以满足新的限制条件）
5. 分组背包 循环顺序（一层：所有的组，二层：倒序费用，三层：当前组中的所有物品）

区间dp

8.31

1. 括号匹配（先处理小区间再处理大区间）

2. 最长回文子序列（法一：求原串和反串的最长公共子序列；法二：）

2.1最长回文子串（法一：manacher；法二：）

bool f[i][j]表示i~j这个区间的元素是不是回文的
if a[i]==a[j] && f[i+1][j-1]==1
	f[i][j]=1;

3. 石子合并（先考虑无环再考虑有环）

4. 凸多边形的三角拆分

5. 田忌赛马（总结之后只有出最强马或者最弱马的情况

其他：

1.最大的不重叠字串和

f[i]表示前i个数（包含第i）的最大子串和
g[i]表示前i个数的最大字串和 g[i]=max(g[i-1],f[i])
h[i]表示后i个数（包含）的最大字串和
枚举分界点，计算最大值

2. 多个

2.1 多个环状

规定从n和1的地方断开
f[i][j][0/1]前i个元素选了j个子串，第i个元素不选/选
最后多判断一种f[n][m+1][1]的情况（首尾相连可以把两个区间看成一个区间