DP 学习笔记

模板及讲解
最基础的DP,包括了背包DP以及一些DP辅助,非常重要。

常见题型(只列举部分题目)
1、前i个物品所用重量为j的最优值
过河(NOIP2005)
乘积最大(NOIP2000)
小朋友的数字(NOIP2013)
守望者的逃离(NOIP2007)
2、前i个物品差值为j的最优值
多米诺骨牌
搭建双塔
3、以xx结尾的最优值
最长上升公共子序列
4、[i,j]区间最优值
沙子合并(NOI1995)
能量项链(NOIP2016)
5、根据题意设多维
方格取数(NOIP2000)
传纸条(NOIP2008)
乌龟棋(NOIP2010)
6、记忆化搜索
滑雪
7、存在性状态
垃圾陷阱
8、[i, n]最优值
ANSOFNU NOIP模拟题-1 T3
9、A在i时,B在f(i)时
Bzoj 1222
10、设$dp(i,j)​$为前$i​$个物品,组成和模$f​$的方案数
Bzoj 3400

------ 本文结束 ------