各类dp
题单介绍
### [$Part$ $1$：背包](https://www.luogu.com.cn/training/556910)
- [P2563 [AHOI2001] 质数和分解](https://www.luogu.com.cn/problem/P2563)
- [P4141 消失之物](https://www.luogu.com.cn/problem/P4141)
- [P2946 [USACO09MAR] Cow Frisbee Team S](https://www.luogu.com.cn/problem/P2946)
- [P1833 樱花](https://www.luogu.com.cn/problem/P1833)
- [P1466 [USACO2.2] 集合 Subset Sums](https://www.luogu.com.cn/problem/P1466)
- [P5020 [NOIP2018 提高组] 货币系统](https://www.luogu.com.cn/problem/P5020)
### [$Part$ $2$：线性dp](https://www.luogu.com.cn/training/556912)
- [P1874 快速求和](https://www.luogu.com.cn/problem/P1874)
- [P1944 最长括号匹配](https://www.luogu.com.cn/problem/P1944)
- [P1020 [NOIP1999 提高组] 导弹拦截](https://www.luogu.com.cn/problem/P1020)
- [P2340 [USACO03FALL] Cow Exhibition G](https://www.luogu.com.cn/problem/P2340)
- [P3842 [TJOI2007] 线段](https://www.luogu.com.cn/problem/P3842)
- [P1103 书本整理](https://www.luogu.com.cn/problem/P1103)
- [P2690 [USACO04NOV] Apple Catching G](https://www.luogu.com.cn/problem/P2690)
- [P8356 「WHOI-1」数列计数](https://www.luogu.com.cn/problem/P8356)
- [P2513 [HAOI2009] 逆序对数列](https://www.luogu.com.cn/problem/P2513)
- [P4933 大师](https://www.luogu.com.cn/problem/P4933)
- [P4310 绝世好题](https://www.luogu.com.cn/problem/P4310)
- [P1439 【模板】最长公共子序列](https://www.luogu.com.cn/problem/P1439)
- [P1868 饥饿的奶牛](https://www.luogu.com.cn/problem/P1868)
- [P10793 『SpOI - R1』Double Champions](https://www.luogu.com.cn/problem/P10793)
- [P1541 [NOIP2010 提高组] 乌龟棋](https://www.luogu.com.cn/problem/P1541)
- [P1006 [NOIP2008 提高组] 传纸条](https://www.luogu.com.cn/problem/P1006)
- [P1668 [USACO04DEC] Cleaning Shifts S](https://www.luogu.com.cn/problem/P1668)
- [P6870 [COCI2019-2020#5] Zapina](https://www.luogu.com.cn/problem/P6870)
- [P2679 [NOIP2015 提高组] 子串](https://www.luogu.com.cn/problem/P2679)
- [P1799 数列](https://www.luogu.com.cn/problem/P1799)
- [P7077 [CSP-S2020] 函数调用](https://www.luogu.com.cn/problem/P7077)
- [P2893 [USACO08FEB] Making the Grade G](https://www.luogu.com.cn/problem/P2893)
- [P2467 [SDOI2010] 地精部落](https://www.luogu.com.cn/problem/P2467)
- [P3847 [TJOI2007] 调整队形](https://www.luogu.com.cn/problem/P3847)
### [$Part$ $3$：记忆化搜索](https://www.luogu.com.cn/training/556917)
- [P2690 [USACO04NOV] Apple Catching G](https://www.luogu.com.cn/problem/P2690)
- [P5635 【CSGRound1】天下第一](https://www.luogu.com.cn/problem/P5635)
### [$Part$ $4$：区间dp](https://www.luogu.com.cn/training/556918)
- [P2858 [USACO06FEB] Treats for the Cows G/S](https://www.luogu.com.cn/problem/P2858)
- [P9325 [CCC 2023 S2] Symmetric Mountains](https://www.luogu.com.cn/problem/P9325)
- [P1775 石子合并（弱化版）](https://www.luogu.com.cn/problem/P1775)
- [P1880 [NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880)
- [P4170 [CQOI2007] 涂色](https://www.luogu.com.cn/problem/P4170)
- [P8675 [蓝桥杯 2018 国 B] 搭积木](https://www.luogu.com.cn/problem/P8675)
- [P3146 [USACO16OPEN] 248 G](https://www.luogu.com.cn/problem/P3146)
- [P10115 [LMXOI Round 1] Placer](https://www.luogu.com.cn/problem/P10115)
- [P6457 [COCI2006-2007#5] IVANA](https://www.luogu.com.cn/problem/P6457)
- [P1063 [NOIP2006 提高组] 能量项链](https://www.luogu.com.cn/problem/P1063)
- [P3205 [HNOI2010] 合唱队](https://www.luogu.com.cn/problem/P3205)
- [P10236 [yLCPC2024] D. 排卡](https://www.luogu.com.cn/problem/P10236)
- [P5851 [USACO19DEC] Greedy Pie Eaters P](https://www.luogu.com.cn/problem/P5851)
- [P1220 关路灯](https://www.luogu.com.cn/problem/P1220)
- [P4342 [IOI1998] Polygon](https://www.luogu.com.cn/problem/P4342)
- [P4302 [SCOI2003] 字符串折叠](https://www.luogu.com.cn/problem/P4302)
- [P2466 [SDOI2008] Sue 的小球](https://www.luogu.com.cn/problem/P2466)
- [P5486 [JLOI2010] 世界杯租房](https://www.luogu.com.cn/problem/P5486)
- [P10600 BZOJ4350 括号序列再战猪猪侠](https://www.luogu.com.cn/problem/P10600)
- [P4766 [CERC2014] Outer space invaders](https://www.luogu.com.cn/problem/P4766)
- [P6879 [JOI 2020 Final] スタンプラリー 3](https://www.luogu.com.cn/problem/P6879)
- [P6701 [POI1997] Genotype](https://www.luogu.com.cn/problem/P6701)
- [P3147 [USACO16OPEN] 262144 P](https://www.luogu.com.cn/problem/P3147)
- [P9493 「SFCOI-3」进行一个列的排](https://www.luogu.com.cn/problem/P9493)
- [P4805 [CCC2016] 合并饭团](https://www.luogu.com.cn/problem/P4805)
- [P7914 [CSP-S 2021] 括号序列](https://www.luogu.com.cn/problem/P7914)
- [P4290 [HAOI2008] 玩具取名](https://www.luogu.com.cn/problem/P4290)
- [P2470 [SCOI2007] 压缩](https://www.luogu.com.cn/problem/P2470)
- [P2145 [JSOI2007] 祖玛](https://www.luogu.com.cn/problem/P2145)
### [$Part$ $5.1$：树形dp](https://www.luogu.com.cn/training/556923)
- [P1481 魔族密码](https://www.luogu.com.cn/problem/P1481)
- [P8625 [蓝桥杯 2015 省 B] 生命之树](https://www.luogu.com.cn/problem/P8625)
- [P8744 [蓝桥杯 2021 省 A] 左孩子右兄弟](https://www.luogu.com.cn/problem/P8744)
- [P5007 DDOSvoid 的疑惑](https://www.luogu.com.cn/problem/P5007)
- [P4362 [NOI2002] 贪吃的九头龙](https://www.luogu.com.cn/problem/P4362)
- [P7103 「C.E.L.U-01」族谱树](https://www.luogu.com.cn/problem/P7103)
- [P4438 [HNOI/AHOI2018] 道路](https://www.luogu.com.cn/problem/P4438)
- [P10783 【MX-J1-T3】『FLA - III』Anxiety](https://www.luogu.com.cn/problem/P10783)
- [P9161 Trees](https://www.luogu.com.cn/problem/P9161)
- [P9437 『XYGOI round1』一棵树](https://www.luogu.com.cn/problem/P9437)
- [P9386 [THUPC 2023 决赛] 大纲](https://www.luogu.com.cn/problem/P9386)
- [P1131 [ZJOI2007] 时态同步](https://www.luogu.com.cn/problem/P1131)
- [P3174 [HAOI2009] 毛毛虫](https://www.luogu.com.cn/problem/P3174)
- [P2015 二叉苹果树](https://www.luogu.com.cn/problem/P2015)
- [P2986 [USACO10MAR] Great Cow Gathering G](https://www.luogu.com.cn/problem/P2986)
- [P7846 「dWoi R2」Arcade hall / 街机厅](https://www.luogu.com.cn/problem/P7846)
- [P9593 「Daily OI Round 1」Block](https://www.luogu.com.cn/problem/P9593)
- [P9584 「MXOI Round 1」城市](https://www.luogu.com.cn/problem/P9584)
- [P1543 [POI2004] SZP](https://www.luogu.com.cn/problem/P1543)
- [P2014 [CTSC1997] 选课](https://www.luogu.com.cn/problem/P2014)
- [P2018 消息传递](https://www.luogu.com.cn/problem/P2018)
- [P3047 [USACO12FEB] Nearby Cows G](https://www.luogu.com.cn/problem/P3047)
- [P4084 [USACO17DEC] Barn Painting G](https://www.luogu.com.cn/problem/P4084)
- [P1270 “访问”美术馆](https://www.luogu.com.cn/problem/P1270)
- [P2899 [USACO08JAN] Cell Phone Network G](https://www.luogu.com.cn/problem/P2899)
- [P2279 [HNOI2003] 消防局的设立](https://www.luogu.com.cn/problem/P2279)
- [P3360 偷天换日](https://www.luogu.com.cn/problem/P3360)
- [P7537 [COCI2016-2017#4] Rima](https://www.luogu.com.cn/problem/P7537)
- [P8981 「DROI」Round 1 距离](https://www.luogu.com.cn/problem/P8981)
- [P8677 [蓝桥杯 2018 国 A] 采油](https://www.luogu.com.cn/problem/P8677)
- [P9634 [ICPC2020 Nanjing R] Monster Hunter](https://www.luogu.com.cn/problem/P9634)
- [P9346 无可奈何花落去](https://www.luogu.com.cn/problem/P9346)
- [P8867 [NOIP2022] 建造军营](https://www.luogu.com.cn/problem/P8867)
- [P10767 「CROI · R2」在相思树下 II](https://www.luogu.com.cn/problem/P10767)
- [P8877 [传智杯 #5 初赛] I-不散的宴会](https://www.luogu.com.cn/problem/P8877)
- [P9669 [ICPC2022 Jinan R] DFS Order 2](https://www.luogu.com.cn/problem/P9669)
- [P6554 Promises I Can't Keep](https://www.luogu.com.cn/problem/P6554)
- [P8595 「KDOI-02」一个网的路](https://www.luogu.com.cn/problem/P8595)
- [P7574 「PMOI-3」子树](https://www.luogu.com.cn/problem/P7574)
- [P8127 [BalticOI 2021 Day2] The Xana coup](https://www.luogu.com.cn/problem/P8127)
- [P8973 『GROI-R1』 继续深潜，为了同一个梦想](https://www.luogu.com.cn/problem/P8973)
- [P6679 [COCI2019-2020#2] Zvijezda](https://www.luogu.com.cn/problem/P6679)
- [P3177 [HAOI2015] 树上染色](https://www.luogu.com.cn/problem/P3177)
- [P6594 [YsOI2020] 换寝室](https://www.luogu.com.cn/problem/P6594)
- [P8280 「MCOI-08」Photoelectric Effect](https://www.luogu.com.cn/problem/P8280)
- [P9210 蓬莱「凯风快晴 −富士火山−」](https://www.luogu.com.cn/problem/P9210)
- [P9414 「NnOI R1-T3」元组](https://www.luogu.com.cn/problem/P9414)
- [P7925 「EVOI-RD2」童年](https://www.luogu.com.cn/problem/P7925)
- [P8009 「Wdsr-3」船往低处流](https://www.luogu.com.cn/problem/P8009)
- [P10406 「SMOI-R1」Company](https://www.luogu.com.cn/problem/P10406)
- [P4084 [USACO17DEC] Barn Painting G](https://www.luogu.com.cn/problem/P4084)
- [P1122 最大子树和](https://www.luogu.com.cn/problem/P1122)
- [P1040 [NOIP2003 提高组] 加分二叉树](https://www.luogu.com.cn/problem/P1040)
- [P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352)
- [P2014 [CTSC1997] 选课](https://www.luogu.com.cn/problem/P2014)
- [P2585 [ZJOI2006] 三色二叉树](https://www.luogu.com.cn/problem/P2585)
- [P2015 二叉苹果树](https://www.luogu.com.cn/problem/P2015)
- [P5658 [CSP-S2019] 括号树](https://www.luogu.com.cn/problem/P5658)
- [P4395 [BOI2003] Gem 气垫车](https://www.luogu.com.cn/problem/P4395)
- [P1273 有线电视网](https://www.luogu.com.cn/problem/P1273)
- [P3047 [USACO12FEB] Nearby Cows G](https://www.luogu.com.cn/problem/P3047)
- [P3698 [CQOI2017] 小Q的棋盘](https://www.luogu.com.cn/problem/P3698)
- [P3177 [HAOI2015] 树上染色](https://www.luogu.com.cn/problem/P3177)
- [P4322 [JSOI2016] 最佳团体](https://www.luogu.com.cn/problem/P4322)
- [P2607 [ZJOI2008] 骑士](https://www.luogu.com.cn/problem/P2607)
- [P4516 [JSOI2018] 潜入行动](https://www.luogu.com.cn/problem/P4516)
### [$Part$ $5.2$：树形dp（神犇版）](https://www.luogu.com.cn/training/561508)
- [P9847 [ICPC2021 Nanjing R] Crystalfly](https://www.luogu.com.cn/problem/P9847)
- [P3574 [POI2014] FAR-FarmCraft](https://www.luogu.com.cn/problem/P3574)
- [P9745 「KDOI-06-S」树上异或](https://www.luogu.com.cn/problem/P9745)
- [P8428 [COCI2020] Pastiri](https://www.luogu.com.cn/problem/P8428)
- [P8089 『JROI-5』Color](https://www.luogu.com.cn/problem/P8089)
- [P3554 [POI2013] LUK-Triumphal arch](https://www.luogu.com.cn/problem/P3554)
- [P5666 [CSP-S2019] 树的重心](https://www.luogu.com.cn/problem/P5666)
- [P6213 「SWTR-4」Collecting Coins](https://www.luogu.com.cn/problem/P6213)
- [P2607 [ZJOI2008] 骑士](https://www.luogu.com.cn/problem/P2607)
- [P3576 [POI2014] MRO-Ant colony](https://www.luogu.com.cn/problem/P3576)
- [P5680 [GZOI2017] 共享单车](https://www.luogu.com.cn/problem/P5680)
- [P4253 [SCOI2015] 小凸玩密室](https://www.luogu.com.cn/problem/P4253)
- [P3596 [POI2015] MOD](https://www.luogu.com.cn/problem/P3596)
- [P3523 [POI2011] DYN-Dynamite](https://www.luogu.com.cn/problem/P3523)
- [P6419 [COCI2014-2015#1] Kamp](https://www.luogu.com.cn/problem/P6419)
- [P3565 [POI2014] HOT-Hotels](https://www.luogu.com.cn/problem/P3565)
- [P6287 [COCI2016-2017#1] Mag](https://www.luogu.com.cn/problem/P6287)
- [P3237 [HNOI2014] 米特运输](https://www.luogu.com.cn/problem/P3237)
- [P3757 [CQOI2017] 老C的键盘](https://www.luogu.com.cn/problem/P3757)
- [P4620 [SDOI2018] 荣誉称号](https://www.luogu.com.cn/problem/P4620)
- [P7581 「RdOI R2」路径权值(distance)](https://www.luogu.com.cn/problem/P7581)
- [P9111 [福建省队集训2019] 最大权独立集问题](https://www.luogu.com.cn/problem/P9111)
- [P8917 [DMOI-R2] 风神瞳（Anemoculus）](https://www.luogu.com.cn/problem/P8917)
- [P8935 [JRKSJ R7] 茎](https://www.luogu.com.cn/problem/P8935)
- [P9476 [_-0 B] 地铁](https://www.luogu.com.cn/problem/P9476)
- [P10674 【MX-S1-T3】电动力学](https://www.luogu.com.cn/problem/P10674)
- [P8975 『GROI-R1』 湖底之城](https://www.luogu.com.cn/problem/P8975)
- [P8288 「DAOI R1」Fireworks](https://www.luogu.com.cn/problem/P8288)
- [P9655 『GROI-R2』 Beside You](https://www.luogu.com.cn/problem/P9655)
- [P10794 『SpOI - R1』架子鼓可以站 C](https://www.luogu.com.cn/problem/P10794)
- [P7841 「C.E.L.U-03」100%不公平的游戏](https://www.luogu.com.cn/problem/P7841)
- [P6478 [NOI Online #2 提高组] 游戏](https://www.luogu.com.cn/problem/P6478)
- [P8227 「Wdoi-5」建立与摧毁的结界](https://www.luogu.com.cn/problem/P8227)
- [P8916 [DMOI-R2] 暗号](https://www.luogu.com.cn/problem/P8916)
- [P10175 「OICon-02」Subtree Value](https://www.luogu.com.cn/problem/P10175)
- [P9663 [ICPC2021 Macao R] Permutation on Tree](https://www.luogu.com.cn/problem/P9663)
- [P9967 [THUPC 2024 初赛] 采矿](https://www.luogu.com.cn/problem/P9967)
- [P5298 [PKUWC2018] Minimax](https://www.luogu.com.cn/problem/P5298)
- [P4492 [HAOI2018] 苹果树](https://www.luogu.com.cn/problem/P4492)
- [P6653 [YsOI2020] 造林](https://www.luogu.com.cn/problem/P6653)
- [P6793 [SNOI2020] 字符串](https://www.luogu.com.cn/problem/P6793)
- [P9487 「LAOI-1」小熊游景点](https://www.luogu.com.cn/problem/P9487)
- [P6803 [CEOI2020] 星际迷航](https://www.luogu.com.cn/problem/P6803)
- [P7498 磁控法则](https://www.luogu.com.cn/problem/P7498)
- [P7359 「JZOI-1」旅行](https://www.luogu.com.cn/problem/P7359)
- [P8290 [省选联考 2022] 填树](https://www.luogu.com.cn/problem/P8290)
- [P8202 [传智杯 #4 决赛] [yLOI2021] 染色](https://www.luogu.com.cn/problem/P8202)
### [$Part$ $6$：数位dp](https://www.luogu.com.cn/training/556933)
- [P4999 烦人的数学作业](https://www.luogu.com.cn/problem/P4999)
- [P4798 [CEOI2015 Day1] 卡尔文球锦标赛](https://www.luogu.com.cn/problem/P4798)
- [P2602 [ZJOI2010] 数字计数](https://www.luogu.com.cn/problem/P2602)
- [P2657 [SCOI2009] windy 数](https://www.luogu.com.cn/problem/P2657)
- [P2518 [HAOI2010] 计数](https://www.luogu.com.cn/problem/P2518)
- [P4124 [CQOI2016] 手机号码](https://www.luogu.com.cn/problem/P4124)
- [P3281 [SCOI2013] 数数](https://www.luogu.com.cn/problem/P3281)
- [P3286 [SCOI2014] 方伯伯的商场之旅](https://www.luogu.com.cn/problem/P3286)
### [$Part$ $7$：单调队列优化dp](https://www.luogu.com.cn/training/556934)
- [P3522 [POI2011] TEM-Temperature](https://www.luogu.com.cn/problem/P3522)
- [P3957 [NOIP2017 普及组] 跳房子](https://www.luogu.com.cn/problem/P3957)
- [P1725 琪露诺](https://www.luogu.com.cn/problem/P1725)
- [P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776)
- [P2627 [USACO11OPEN] Mowing the Lawn G](https://www.luogu.com.cn/problem/P2627)
- [P3089 [USACO13NOV] Pogo-Cow S](https://www.luogu.com.cn/problem/P3089)
- [P3572 [POI2014] PTA-Little Bird](https://www.luogu.com.cn/problem/P3572)
- [P2034 选择数字](https://www.luogu.com.cn/problem/P2034)
- [P4544 [USACO10NOV] Buying Feed G](https://www.luogu.com.cn/problem/P4544)
- [CF372C Watching Fireworks is Fun](https://www.luogu.com.cn/problem/CF372C)
- [P5665 [CSP-S2019] 划分](https://www.luogu.com.cn/problem/P5665)
- [P1973 [NOI2011] NOI 嘉年华](https://www.luogu.com.cn/problem/P1973)
- [P2569 [SCOI2010] 股票交易](https://www.luogu.com.cn/problem/P2569)
- [P4852 yyf hates choukapai](https://www.luogu.com.cn/problem/P4852)