【动态规划】值得一做的dp好题

dp问题分为基本（特殊类型）dp问题和数据结构优化 dp， 由于想到 dp 题目千千万万，很难筛选，于是，自己筛了一些比较上手的 dp好题，希望大家喜欢 本题单不推荐按照难度顺序做题。 如有其余好的dp题欢迎私信我，如有错误欢迎指出。 当然，也借此宣传一下我的dp学习笔记[Link](https://www.luogu.com.cn/blog/zzds-qfxyyyds/about-dp) 关于本题单涉及到的一些问题： ### 区间 dp： - 一般在序列上进行 - 当前区间的答案可以通过枚举断点的方式由两段相邻的子区间的答案合并而来 时间复杂度：$O(n)$ 推荐题目： [P1775 石子合并（弱化版）](https://www.luogu.com.cn/problem/P1775) [P1880 [NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880) ### 数位 dp - 其实就是一位一位做 dp - 一般用**记忆化搜索**来做 - 注意处理前导 0，优化在于合并答案相同的状态 时间复杂度：通常与数位有关 推荐题目： [CF276D Little Girl and Maximum XOR](https://www.luogu.com.cn/problem/CF276D) [P2602 [ZJOI2010] 数字计数](https://www.luogu.com.cn/problem/P2602) ### 排列 dp - 罕见的 dp 问题，dp 的对象一般都为 `1~n` 的 - 一般情况下，都用 $dp_i$ 来表示 `1~i` 的排列 - 其他题目的转移一般也会是从小到大或者从大到小 推荐题目： [CF1666F Fancy Stack](https://www.luogu.com.cn/problem/CF1666F) [P7406 [JOI 2021 Final] 集合写真](https://www.luogu.com.cn/problem/P7406) 由于比较罕见，这块的题目不多，大家忍耐一下zzds太弱/kel ### 树形 dp - 在树上进行的 dp - 树形 dp 都是由上向下搜索（转移），整个过程其实就是一个从上向下的 dfs - 在树形 dp 中要合并**恰当的合并子节点的答案** 时间复杂度：$O(n)$ 推荐题目： [P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352) [P2014 [CTSC1997] 选课](https://www.luogu.com.cn/problem/P2014) [P1273 有线电视网](https://www.luogu.com.cn/problem/P1273) [P3174 [HAOI2009] 毛毛虫](https://www.luogu.com.cn/problem/P3174)