基础准备 当一个问题较为复杂，而它与子问题之间表现出良好的关系时，我们通常可以考虑由子问题推出原问题的答案。然而某些子问题会在被利用于求解原问题时重复求解，使得复杂度提高；因为原问题存在多种子问题的分解方式，有可能因为选择了不当的分解方式而使得复杂度提高。上述两个问题分别对应了 问题与子问题的求解顺序问题 和 问题状态的设计问题 ，我认为 dp 的核心就是探讨这两个问题的做法，即 dp 中的 dp顺序 和 dp状态，当然 dp优化 也在 dp 状态这一块中占据了很大的位置。这两者（或者说三者）是互相联系的，通常需要同时进行考虑。 dp 可以解决的问题类型有二：最优化问题和求某个值，如果是求某个值的话更加偏向于递推问题或计数类（说实话这两类问题有什么区别吗。。。 各种 dp 模型 区间 dp ：虽然说是区间 dp ，但早已从“区间”二字拓展开了。这类 dp 的问题通常能被描述成一个二元组 (x,y) ，而其从子问题的合并则是将两个二元组合并。 背包 dp： 这类问题要求规划一些物品的选择方案以实现在代价和法的情况下价值最大化，所以问题状态通常有两种：价值总和和容量，对应的每个物品有两个属性：价值和代价。 物品之间的 dp 顺序通常无关全局答案紧要，有时合理安排物品顺序可以做到子问题的重复利用。 同时背包在物品顺序这一维上还具有一些神秘的可合并性。 01 背包：最简单的背包，每个物品只有两种选择状态（可分别用 0 和 1 来表示，即名称的由来） 完全背包：每个物品有无数个。 多重背包：每个物品的数量给定。 else：通常都是物品与物品之间有某些依赖关系，然后要综合利用以上三种背包综合解决。 状压 dp：通常问题的某些维度中含有数量复杂度较高的类型，比如将一个大小为 n 的集合的所有状态作为一个维度，其复杂度是 O(2^n) 的，又或者是一个排列，那就是 O(n!) 。但由于这些...