动态规划

$\qquad\!\!$在解决 dp 问题时，主要要从两点思考： - 1、**状态**： $\qquad\!\!$通常来讲，状态的设立因题而异，大多数与答案的意义相同（dp数组 中的某个值即为答案）或者与答案具有直接联系（比如再经过某种统计即可得到答案）。 $\qquad\!\!$对于很难一眼看出状态（比如答案无法转移）的题，我们就要利用 dp的本质：“把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。”和 dp 最重要的一个性质：“无后效性”去推理。 $\qquad\!\!$根据无后效性，我们可以假设在这个阶段之前的阶段（注意，这个“之前”表示的是 dp转移 上的之前，可能是空间上的之前、数位上的之前、拓扑序上的之前……）都已经进行了最优化的决策。根据 dp的本质，如果之前的阶段的最优决策映射出的一种“结果”能以 **某种方式** 转移到此阶段的这种“结果”，且此时的这种“结果”也恰好为此时的最优化决策的这种映射，那么这种“结果”即为 dp的状态。 - 2、**转移方程**： $\qquad\!\!$通常来讲，转移方程的确立也是因题而异的，不过在得出了正确的状态之后，转移方程的确立方式一般比较显然。 $\qquad\!\!$前文中加粗的的“**某种方式**”，即可理解为一种状态到状态的转移方式。我们在将其具体化以后，即可得到对于相邻状态的转移方程。同时，对于很多题目的转移方程可以利用数学的计算或者数据结构的辅助得以在复杂度上得以化简，即为 dp的优化。 - 3、**实现方法**： $\qquad\!\!$一般来说，动态规划可以通过递推和记忆化搜索两种方式实现。 ---------- ## 目录： - 1、[基础动态规划](https://www.luogu.com.cn/blog/226623/ji-chu-dong-tai-gui-hua)： - ①、线性dp - ②、多维dp - ③、背包dp： - (1)、01背包 - (2)、完全背包 - (3)、01背包前 $k$ 优解 - (4)、分组背包 - (5)、多重背包 - 1)、二进制分组、 - 2)、单调队列优化 - (6)、混合背包 - (7)、二维费用 - 2、[进阶动态规划](https://www.luogu.com.cn/blog/226623/jin-jie-dong-tai-gui-hua)： - ①、[树形dp](https://www.luogu.com.cn/blog/226623/shu-xing-dp)： - (1)、基础树形dp - (2)、递归前转移树形dp - (3)、递归后转移树形dp - (4)、树上01背包 - (5)、树上分组背包 - (6)、基础换根dp - (7)、[进阶换根dp](https://www.luogu.com.cn/blog/226623/jin-jie-huan-gen-dp) - (8)、基环树之树形dp+环形dp - (9)、基环树之开环直接树形dp - ②、DAG上的dp（拓扑排序） - ③、环形dp - ④、区间dp - ⑤、状压dp - ⑥、数位dp - ⑦、期望dp - ⑧、[dp计数](https://www.luogu.com.cn/blog/226623/ti-jie-T137853-ju-zhen-ge-ming) - ⑨、[dp优化](https://www.luogu.com.cn/blog/226623/dp-you-hua)： - (1).斜率优化 - (2).四边形不等式优化 - (3).数据结构优化： - ①.单调栈/单调队列优化 - ②.树状数组优化 - ③.线段树优化 - ④.矩阵快速幂优化