本文意在总结常见的动态规划的题型和模板，并不断更新。

动态规划

• 本质：暴力枚举，原问题不断拆分为子问题。
• 思考思路：选或不选（大部分是），枚举选哪个
• 解决方法：记忆化搜索（较容易）或者 dp 数组递推（较难）
• 关于计算 $dp$ 时间复杂度的理解：1. 子问题个数 × 得到子问题解的复杂度。 2. 状态个数 × 得到每个状态的复杂度

具体 题型和模板 分别参考以下题解：

1. 带权的日程选择dp问题（进阶）

• 【关键问题：日程重叠带权重；题目类型：密集分组 dp / 离散化+二分 / 日程个数限制二维 dp 】

2. 打家劫舍不相邻问题（基础）

• 【关键问题：数组选择元素不能相邻；题目类型：普通数组 / 环形数组】

3. 数位dp模板和题型总结（进阶）

• 【关键问题：考虑每一个 数位 / 存在上下界 / 数据范围特别大 往往超过 $10^9$ 】

4. 01背包、完全背包、多维背包、分组背包问题（基础）

• 【关键问题：容量有限下的最优解；题目类型：01背包 / 完全背包 （求方案数的时候注意排列型和组合型）/ 多维背包 / 分组背包 】

5. 最长公共子序列问题（基础）

• 【关键问题：在不改变原有数组元素顺序的情况下，得到一个满足题目要求的子序列】

6. 区间dp（进阶）

• 【关键问题：大区间向小区间转移合并，区间长度往往是递归边界】

7. 解决线性枚举时存在区间约束的dp问题（基础）

• 【关键问题：线性枚举 时存在 区间约束，不能任意枚举】

8. 换根dp（进阶）

• 【关键问题：梳理清楚 换根 时， 状态转移 的方式】

9. 值域dp（进阶）

• 【关键问题：状态转移的方式不再是索引 $i$ ，而是值 $x$ 】

缓慢更新 ing ，实在是有点多。。。