简单dp刷题回忆录

关于简单dp的一定要掌握的一些经典问题:

最长不下降子序列/最长不上升子序列:合唱队形($N^2$解法),导弹拦截($N$ ^ $logN$做法,但是不能保存最优解的序列)

求最长回文子串 小A的回文串

悬线法:棋盘制作 玉蟾宫

求最长连续字段和 饥饿的牛

二维矩阵最大连续字段和: To the Max

---

一维的线性dp问题

这一类问题的核心一般是当前的状态可以直接从前一次的状态转移过来,基本上是该位置的左右两边走到当前的位置，并且前一次的状态位置什么的大都是可以确定的，是有限个的，对于转移方程的推导来说类似于数列递推公式的推导(甚至有些是可以求出通项的)，或者带有计数dp的属性

举例:
舔狗舔到最后一无所有

免费馅饼

钉子和小球

传球游戏

小A买彩票

失衡天平

Music Problem

简单瞎搞题 [由$bitset$优化的$dp题$]

乌龟棋

摆花

货币系统

音量调节

Running

---

其次是一些类区间dp的线性dp问题

这种题目大致都是一维线性的，但是同前面的简单线性dp不同，这种类似的题目大都可以抽象为对于一段序列我们花费j次操作得到i点贡献，然后对于转移，因为此时我们的之前状态的位置是不确定的，我们一般都是枚举之前操作j-1时的位置，然后加上我们最后一次操作的贡献，此类问题的递推方向大都是单向的，而前面的线性dp的推导方向是有限多向的
举例：
花店橱窗

购物

牛牛的旅游纪念品 [本题算是这个思想部分时候的优化??]

统计单词个数

---

然后是跑图形dp的问题

对于这种dp问题大都是给出了一个邻接表一样的矩阵图，然后给点一个起点和终点，问到终点的路线数或者得分数之类的。对于这种题目，大致都是由每一个可以到达该位置的点进行转移，大致都是从左到右从上到下的转移方向

举例：

过河卒

「木」迷雾森林

传纸条 同时走两条路的跑图题

方格取数 同上

飞扬的小鸟

金币馅饼

---

然后是背包类问题

01背包问题:装箱问题 采药 开心的金明 CSL分苹果

带有贪心的01背包问题: 美味菜肴

对于某件物品(未知)不能带的背包问题:Min酱要旅行

带有主附件或者从属性质的背包问题:

1.金明的预算方案
[附件不可以单独购买,主件和附件是有联系的,附件数已知] 方法是一起dp
2. 队伍配置
[附件不可以单独购买,但是主件和附件没有联系,附件数未知] 方法是分开dp
3.Video Game Troubles
[附件不可单独购买,主体与附件有联系,附件数未知] 方法是循环+分开dp

---

纯纯的区间dp问题(但是有些难度较大,解法不易想到)

主要做法就是枚举区间的长度和左右端点,然后找一个区间的中转点进行转移

合并回文子串

取数游戏2

wyh的问题

矩阵取数游戏

石子合并

凸多边形的划分 有点难想的区间dp

能量项链

涂色PAINT [区间染色的经典问题]

跳跳跳

---

有趣的杂题

过河

---

有难度的杂题

最大子矩阵

粉刷匠 区间涂色问题+分组背包问题