Part 4.1-4.4 动态规划

# Part 4 动态规划 > 动态规划是一种重要的思维方法，通过利用已有的子问题信息高效求出当前问题的最优解。 ## Part 4.1 线性动态规划 > 线性动态规划，即具有线性阶段划分的动态规划。 - [P1216 数字三角形](https://www.luogu.com.cn/problem/P1216) - [P1020 导弹拦截](https://www.luogu.com.cn/problem/P1020) - [P1091 合唱队形](https://www.luogu.com.cn/problem/P1091) - [P1095 守望者的逃离](https://www.luogu.com.cn/problem/P1095) - [P1541 乌龟棋](https://www.luogu.com.cn/problem/P1541) - [P1868 饥饿的奶牛](https://www.luogu.com.cn/problem/P1868) - [P2679 子串](https://www.luogu.com.cn/problem/P2679) - [P2501 [HAOI2006]数字序列](https://www.luogu.com.cn/problem/P2501) - [P3336 [ZJOI2013]话旧](https://www.luogu.com.cn/problem/P3336) - [P3558 [POI2013]BAJ-Bytecomputer](https://www.luogu.com.cn/problem/P3558) - [P4158 [SCOI2009]粉刷匠](https://www.luogu.com.cn/problem/P4158) - [P5301 [GXOI/GZOI2019]宝牌一大堆](https://www.luogu.com.cn/problem/P5301) ## Part 4.2 背包动态规划 > 背包动态规划是线性动态规划中特殊的一类，NOIP中考到的次数也不少。 - [P1048 采药](https://www.luogu.com.cn/problem/P1048) - [P1060 开心的金明](https://www.luogu.com.cn/problem/P1060) - [P1855 榨取kkksc03](https://www.luogu.com.cn/problem/P1855) - [P5020 货币系统](https://www.luogu.com.cn/problem/P5020) - [P1757 通天之分组背包](https://www.luogu.com.cn/problem/P1757) - [P1064 金明的预算方案](https://www.luogu.com.cn/problem/P1064) - [P2946 [USACO09MAR]Cow Frisbee Team](https://www.luogu.com.cn/problem/P2946) - [P1156 垃圾陷阱](https://www.luogu.com.cn/problem/P1156) - [P5322 [BJOI2019]排兵布阵](https://www.luogu.com.cn/problem/P5322) - [P5289 [十二省联考2019]皮配](https://www.luogu.com.cn/problem/P5289) ## Part 4.3 区间动态规划 > 区间动态规划一般以区间作为动态规划的阶段。 - [P1880 [NOI1995]石子合并](https://www.luogu.com.cn/problem/P1880) - [P3146 [USACO16OPEN]248](https://www.luogu.com.cn/problem/P3146) - [P1063 能量项链](https://www.luogu.com.cn/problem/P1063) - [P1005 矩阵取数游戏](https://www.luogu.com.cn/problem/P1005) - [P4170 [CQOI2007]涂色](https://www.luogu.com.cn/problem/P4170) - [P4302 [SCOI2003]字符串折叠](https://www.luogu.com.cn/problem/P4302) - [P2466 [SDOI2008]Sue的小球](https://www.luogu.com.cn/problem/P2466) ## Part 4.4 树形动态规划 > 树形动态规划，即在树上进行的动态规划。 > > 因为树的递归性质，树形动态规划一般都是递归求解的。 - [P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352) - [P1040 加分二叉树](https://www.luogu.com.cn/problem/P1040) - [P1122 最大子树和](https://www.luogu.com.cn/problem/P1122) - [P1273 有线电视网](https://www.luogu.com.cn/problem/P1273) - [P2014 选课](https://www.luogu.com.cn/problem/P2014) - [P2585 [ZJOI2006]三色二叉树](https://www.luogu.com.cn/problem/P2585) - [P3047 [USACO12FEB]Nearby Cows](https://www.luogu.com.cn/problem/P3047) - [P3698 [CQOI2017]小Q的棋盘](https://www.luogu.com.cn/problem/P3698) - [P5658 括号树](https://www.luogu.com.cn/problem/P5658) - [P2607 [ZJOI2008]骑士](https://www.luogu.com.cn/problem/P2607) - [P3177 [HAOI2015]树上染色](https://www.luogu.com.cn/problem/P3177) - [P4395 [BOI2003]Gem](https://www.luogu.com.cn/problem/P4395) - [P4516 [JSOI2018]潜入行动](https://www.luogu.com.cn/problem/P4516)