DP Part I

来源于[这里](https://www.luogu.com.cn/blog/205125/dong-tai-gui-hua-ge-post)。 进阶版：[DP Part II](https://www.luogu.com.cn/training/242725)。 ### 线性DP 本题单。 - [P1002 [NOIP2002 普及组] 过河卒](https://www.luogu.com.cn/problem/P1002) - [P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles](https://www.luogu.com.cn/problem/P1216) - [P2758 编辑距离](https://www.luogu.com.cn/problem/P2758) - [P1020 [NOIP1999 普及组] 导弹拦截](https://www.luogu.com.cn/problem/P1020) - [P3903 导弹拦截III](https://www.luogu.com.cn/problem/P3903) - [P1439 【模板】最长公共子序列](https://www.luogu.com.cn/problem/P1439) - [P1280 尼克的任务](https://www.luogu.com.cn/problem/P1280) - [P1437 [HNOI2004] 敲砖块](https://www.luogu.com.cn/problem/P1437) ### 区间DP 这部分的子题单：[区间DP](https://www.luogu.com.cn/training/241470)。 - [P1880 [NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880) - [P1435 [IOI2000] 回文字串 / [蓝桥杯 2016 省] 密码脱落](https://www.luogu.com.cn/problem/P1435) - [P3205 [HNOI2010]合唱队](https://www.luogu.com.cn/problem/P3205) - [P1063 [NOIP2006 提高组] 能量项链](https://www.luogu.com.cn/problem/P1063) - [P1220 关路灯](https://www.luogu.com.cn/problem/P1220) - [CF607B Zuma](https://www.luogu.com.cn/problem/CF607B) - [P1005 [NOIP2007 提高组] 矩阵取数游戏](https://www.luogu.com.cn/problem/P1005) - [P2339 [USACO04OPEN]Turning in Homework G](https://www.luogu.com.cn/problem/P2339) - [UVA1626 括号序列 Brackets sequence](https://www.luogu.com.cn/problem/UVA1626) - [P2466 [SDOI2008] Sue 的小球](https://www.luogu.com.cn/problem/P2466) - [P4302 [SCOI2003]字符串折叠](https://www.luogu.com.cn/problem/P4302) - [P2470 [SCOI2007]压缩](https://www.luogu.com.cn/problem/P2470) - [P5154 数列游戏](https://www.luogu.com.cn/problem/P5154) ### 树形DP 这部分的子题单：[树形DP](https://www.luogu.com.cn/training/241374)。 - [P1122 最大子树和](https://www.luogu.com.cn/problem/P1122) - [P2016 战略游戏](https://www.luogu.com.cn/problem/P2016) - [P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352) - [P2015 二叉苹果树](https://www.luogu.com.cn/problem/P2015) - [P1040 [NOIP2003 提高组] 加分二叉树](https://www.luogu.com.cn/problem/P1040) - [P3698 [CQOI2017]小Q的棋盘](https://www.luogu.com.cn/problem/P3698) - [P1131 [ZJOI2007] 时态同步](https://www.luogu.com.cn/problem/P1131) - [P2279 [HNOI2003]消防局的设立](https://www.luogu.com.cn/problem/P2279) - [P2014 [CTSC1997] 选课](https://www.luogu.com.cn/problem/P2014) - [P1273 有线电视网](https://www.luogu.com.cn/problem/P1273) - [P3478 [POI2008] STA-Station](https://www.luogu.com.cn/problem/P3478) - [P2986 [USACO10MAR] Great Cow Gathering G](https://www.luogu.com.cn/problem/P2986) - [P3047 [USACO12FEB]Nearby Cows G](https://www.luogu.com.cn/problem/P3047) - [CF1187E Tree Painting](https://www.luogu.com.cn/problem/CF1187E) - [CF708C Centroids](https://www.luogu.com.cn/problem/CF708C) - [P6419 [COCI2014-2015#1] Kamp](https://www.luogu.com.cn/problem/P6419) - [P1453 城市环路](https://www.luogu.com.cn/problem/P1453) - [P4381 [IOI2008] Island](https://www.luogu.com.cn/problem/P4381) - [P2495 [SDOI2011] 消耗战](https://www.luogu.com.cn/problem/P2495) - [P3233 [HNOI2014]世界树](https://www.luogu.com.cn/problem/P3233) - [CF1009F Dominant Indices](https://www.luogu.com.cn/problem/CF1009F) ### 数位DP 这部分的子题单：[数位DP](https://www.luogu.com.cn/training/241450)。 - [P4317 花神的数论题](https://www.luogu.com.cn/problem/P4317) - [P2602 [ZJOI2010] 数字计数](https://www.luogu.com.cn/problem/P2602) - [P2657 [SCOI2009] windy 数](https://www.luogu.com.cn/problem/P2657) - [P4124 [CQOI2016]手机号码](https://www.luogu.com.cn/problem/P4124) - [P6754 [BalticOI 2013 Day1] Palindrome-Free Numbers](https://www.luogu.com.cn/problem/P6754) - [P3413 SAC#1 - 萌数](https://www.luogu.com.cn/problem/P3413) - [P6218 [USACO06NOV] Round Numbers S](https://www.luogu.com.cn/problem/P6218) - [P3286 [SCOI2014]方伯伯的商场之旅](https://www.luogu.com.cn/problem/P3286) ### 状压DP 这部分的子题单：[状压DP](https://www.luogu.com.cn/training/356598)。 - [P1896 [SCOI2005] 互不侵犯](https://www.luogu.com.cn/problem/P1896) - [P3694 邦邦的大合唱站队](https://www.luogu.com.cn/problem/P3694) - [P2704 [NOI2001] 炮兵阵地](https://www.luogu.com.cn/problem/P2704) - [P1879 [USACO06NOV]Corn Fields G](https://www.luogu.com.cn/problem/P1879) - [P3092 [USACO13NOV]No Change G](https://www.luogu.com.cn/problem/P3092) - [P7145 [THUPC2021 初赛] 合法序列](https://www.luogu.com.cn/problem/P7145) ### 插头DP 这部分的子题单：[插头DP](https://www.luogu.com.cn/training/355978)。 - [P1879 [USACO06NOV] Corn Fields G](https://www.luogu.com.cn/problem/P1879) - [AT_abc211_e [ABC211E] Red Polyomino](https://www.luogu.com.cn/problem/AT_abc211_e) - [CF762D Maximum path](https://www.luogu.com.cn/problem/CF762D) - [UVA11270 Tiling Dominoes](https://www.luogu.com.cn/problem/UVA11270) - [P5074 Eat the Trees](https://www.luogu.com.cn/problem/P5074) - [P4262 [Code+#3] 白金元首与莫斯科](https://www.luogu.com.cn/problem/P4262) - [P5056 【模板】插头 dp](https://www.luogu.com.cn/problem/P5056) - [P2289 [HNOI2004] 邮递员](https://www.luogu.com.cn/problem/P2289) - [P1713 麦当劳叔叔的难题](https://www.luogu.com.cn/problem/P1713) - [P3272 [SCOI2011] 地板](https://www.luogu.com.cn/problem/P3272) - [P3190 [HNOI2007] 神奇游乐园](https://www.luogu.com.cn/problem/P3190) - [CF845F Guards In The Storehouse](https://www.luogu.com.cn/problem/CF845F) - [P3886 [JLOI2009] 神秘的生物](https://www.luogu.com.cn/problem/P3886) - [P4294 [WC2008] 游览计划](https://www.luogu.com.cn/problem/P4294) - [UVA1214 Manhattan Wiring](https://www.luogu.com.cn/problem/UVA1214) - [P3170 [CQOI2015] 标识设计](https://www.luogu.com.cn/problem/P3170) - [P2337 [SCOI2012] 喵星人的入侵](https://www.luogu.com.cn/problem/P2337) - [P1933 [NOI2010] 旅行路线](https://www.luogu.com.cn/problem/P1933) - [UVA10572 Black & White](https://www.luogu.com.cn/problem/UVA10572) - [P3290 [SCOI2016] 围棋](https://www.luogu.com.cn/problem/P3290) - [SP2159 CAKE3 - Delicious Cake](https://www.luogu.com.cn/problem/SP2159) - [UVA10531 Maze Statistics](https://www.luogu.com.cn/problem/UVA10531) - [P3314 [SDOI2014] 电路板](https://www.luogu.com.cn/problem/P3314)