[算法学习笔记] 动态规划合集
动态规划本质上是 状态的合并。我们用一个或多个维度的数组来表示出题目所有的状态。在考虑压缩状态的时候想想压缩掉这一维，其他的维度可以表示题目所有的状态呢？会不会出现不该合并的合并到一起呢？
对于优化，我们一般先写出朴素状态转移方程，再考虑压缩状态，单调队列，线段树等优化。
对于一些套路性问题，例如背包模型，在套用的时候也应当考虑状态设计是否出现问题。
对于一些状态很复杂的题目，直接记忆化搜索。
下面给出目前学习到的动态规划。
-
动态规划入门：0基础带你入门dp
-
背包模型
- 背包模型总结：背包模型
- 多重背包下的二进制分组优化：算法学习笔记 二进制拆分
-
区间dp：合并石子模型：算法学习笔记 区间dp之合并石子模型
-
树上 dp，常用记忆化搜索解决
-
前置知识：树的常用操作：树的常用操作
-
树上 dp 解题报告：树上dp
-
延伸：换根 dp：换根dp
-
-
状压 dp：暴力的枚举所有状态
- 状压 dp 解题报告 状压 dp
-
优化
-
压缩状态
-
单调队列：单调队列优化 dp
-
以上目录为集中处理的动态规划类型，还有一些零散的刷题笔记，这里不再列举。