【动态规划】从入门到NOI

### 0x01 背包 背包是学习 dp 的开始。背包主要是背模板。当然，有些题也需要进行灵活地变化后才能进行背包。 **模板背包练习题：** - [P1048 采药](https://www.luogu.com.cn/problem/P1048) 简单 01 背包板子 - [P1616 疯狂的采药](https://www.luogu.com.cn/problem/P1616) 简单完全背包板子 - [P1757 通天之分组背包](https://www.luogu.com.cn/problem/P1757) 分组背包模板题 **背包应用练习题** - [P1064 金明的预算方案](https://www.luogu.com.cn/problem/P1064) 01 背包的变形，带有附件 - [CF730J Bottles](https://www.luogu.com.cn/problem/CF730J) 看起来不是背包，实际上就是转化题意后的 01 背包 - [CF19B Checkout Assistant](https://www.luogu.com.cn/problem/CF19B) 也是一道 01 背包的变形 - [P1941 飞扬的小鸟](https://www.luogu.com.cn/problem/P1941) 完全背包+01背包 **其它的背包练习题** - [P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776) 单调队列优化多重背包 ### 0x02 线性dp 线性dp是比较基本的dp。但到现在，dp已经不是背板子就能解决的问题了，需要仔细认真地推式子。 ---- **线性dp题目** - [P1115 最大子段和](https://www.luogu.com.cn/problem/P1115) 线性dp中的经典题 - [P2758 编辑距离](https://www.luogu.com.cn/problem/P2758) 线性dp中的经典题 - [P1439 【模板】最长公共子序列](https://www.luogu.com.cn/problem/P1439) 别看它叫模板，你用暴力 $n^2$ dp还过不了，要用二分优化。 - [P1020 导弹拦截](https://www.luogu.com.cn/problem/P1020) 这道题其实就是要求一个最长单调不升子序列和一个最长单调上升子序列，也是要用二分优化到 $O(n\log n)$ - [P1095 守望者的逃离](https://www.luogu.com.cn/problem/P1095) 在时间轴上dp - [P1006 传纸条](https://www.luogu.com.cn/problem/P1006) 很简单的暴力dp ### 0x03 区间dp 顾名思义，区间dp就是在一段区间上dp，求出答案 区间dp具有很大的模板性，一般分为三个循环： - 枚举区间长度 - 枚举区间起点 - 枚举区间分割点，并更新小区间最优解 由此可以看出，能进行区间dp的必要条件就是大区间的答案等于分成任意两个小区间后进行计算的答案。 - [P2858 Treats for the Cows G/S](https://www.luogu.com.cn/problem/P2858) 区间dp入门题 - [P1880 石子合并](https://www.luogu.com.cn/problem/P1880) 最经典的一道区间dp题 - [P1063 能量项链](https://www.luogu.com.cn/problem/P1063) 也是十分经典的一道区间dp - [P4170 涂色](https://www.luogu.com.cn/problem/P4170) 也很经典，不过不是那么经典 ### 0x04 状压dp 将状态压缩成二进制数进行dp。这种题目十分明显：当数据范围特别小而无法进行搜索的时候，就要用状压dp了。 - [P3052 Cows in a Skyscraper G](https://www.luogu.com.cn/problem/P3052) 模板 - [P1896 互不侵犯](https://www.luogu.com.cn/problem/P1896) 也是模板 - [P2704 炮兵阵地](https://www.luogu.com.cn/problem/P2704) 要加上空间优化的状压dp