目录

• 区间dp
• 树形dp
• 练习

区间dp

简单来说区间dp解决的是区间求最小代价等问题 ，通常转移方程为f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+cost)。其中cost为转移的额外花费。

树形dp

树形dp解决的是树上的dp问题，如各种操作后的距离和，权值和最小等问题，一般要用dfs来转移。

练习

下面是已经ac的题(题号为洛谷题号)
P4302,P1220,P2014,P2015,P3177,P1131,P1864