低年级组集训 第四周：动态规划
题单介绍
## 一、递推，记忆化搜索与DP入门
题单：
* [P1192 台阶问题](https://www.luogu.com.cn/problem/P1192)
* [P1002 [NOIP2002 普及组] 过河卒](https://www.luogu.com.cn/problem/P1002)
* [P1464 Function](https://www.luogu.com.cn/problem/P1464)
* [P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles](https://www.luogu.com.cn/problem/P1216)
* [P1434 [SHOI2002] 滑雪](https://www.luogu.com.cn/problem/P1434)
## 二、线性DP
线性DP按照线性的维度状态进行转移，是DP中形式较为基础的一种（当然，形式基础不等于难度简单）。
线性DP中有两个比较常见的模型：最长上升子序列和最长公共子序列。由于洛谷上这两题的数据规模都过大（必须使用额外的技巧），因此我们不将其放入题单中，仅供大家学习参考。
* 最长上升子序列：[P1020 [NOIP1999 普及组] 导弹拦截](https://www.luogu.com.cn/problem/P1020)（满分200，需拿到前100分）
* 最长公共子序列：[P1439 【模板】最长公共子序列](https://www.luogu.com.cn/problem/P1439)（需拿到前50分）
题单：
* [P1091 [NOIP2004 提高组] 合唱队形](https://www.luogu.com.cn/problem/P1091)
* [P1095 [NOIP2007 普及组] 守望者的逃离](https://www.luogu.com.cn/problem/P1095)
## 三、背包DP
基础背包问题分别有：完全背包，01背包，二维费用背包，多重背包与分组背包。在后期，我们还可以学习树上背包和多重背包的单调队列优化。
题单：
* [P1616 疯狂的采药](https://www.luogu.com.cn/problem/P1616)（完全背包）
* [P1048 [NOIP2005 普及组] 采药](https://www.luogu.com.cn/problem/P1048)（01背包）
* [P1164 小A点菜](https://www.luogu.com.cn/problem/P1164)（01背包）
* [P1855 榨取kkksc03](https://www.luogu.com.cn/problem/P1855)（二维费用背包）
* [P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776)（多重背包）
* [P1757 通天之分组背包](https://www.luogu.com.cn/problem/P1757)（分组背包）
* [P5020 [NOIP2018 提高组] 货币系统](https://www.luogu.com.cn/problem/P5020)
## 四、扩展DP（区间/环形DP，DAG上的DP，树形DP）
题单：
* [P1880 [NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880)（区间DP，破环成链）
* [P1063 [NOIP2006 提高组] 能量项链](https://www.luogu.com.cn/problem/P1063)（区间DP）
* [P2196 [NOIP1996 提高组] 挖地雷](https://www.luogu.com.cn/problem/P2196)（DAG上DP，题中的路线都是单向的）
* [P1807 最长路](https://www.luogu.com.cn/problem/P1807)（DAG上DP）
* [P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352)（树形DP）
* [P1040 [NOIP2003 提高组] 加分二叉树](https://www.luogu.com.cn/problem/P1040)