DP
必要的
本文仅凭我的低水平理解写出， 确实对DP不擅长， 所以写一篇文章理一理， 所以很多内容不会将很清楚， 甚至有可能只有我能看懂， 可能在未来会逐渐完善。
据我现在的理解， DP 似乎与 数学归纳法 是等价的？ 我们钦定 \(f(k)\) 是正确的， 只要能够推出 \(f(k + 1)\) 是正确的， 那么就都是正确的。
我们再考虑 DP 的中文名： 动态规划 再翻译一下就是： 动态的规划
以此为引， 讲一下写 DP 一些重要的东西。
-
设计状态， 其实就是上文的 \(f(x)\)， 但是一般不止一个变量， 可以是 \(f(x, y, z)\)等等， \(x, y, z\) 一般是得出答案所必需的一些信息， \(f\)函数的值一般就是答案或者与答案非常相关。
-
设计转移， 转移实际上是依托于状态设计的， 状态设计对了， 转移就顺水推舟得到了， 一般就是考虑 \(f(x)\) 怎么推出 \(f(x + 1)\)。
-
最优子结构， 其实就是考虑非线性的问题， 对标 \(f(k)\) 推出 \(f(k + 1)\)找到一个小结构， 很多个小结构就可以推出全局， 比如树的最优子结构一般就是子树。
背包
典中典
其实我觉得最重要的就是理解完全背包的思想， 顺序枚举， 把选取的结果累起来， 就可以实现选多个。
01背包
完全背包
多重背包
分组背包
有依赖的背包（树型）
线性DP
难在状态， 不要看他很基础， 他可以出的很难， 有些时候必须要状态设计的很巧妙。
区间DP
难在转移， 状态比较无脑， 就是小区间推向大区间。
树型DP
难在转移， 状态一般就是子树。
状压DP
难在状态， 我把它看作多维的线性DP， 我们不可能手开那么多维数组， 所以压成了进制数。
概期DP
难在抽象， 要想学会， 首先得对概率期望熟悉， 有数学知识打基础， 反正我还不怎么会。
计数DP
难在转移， 不重不漏很关键， 一般计数的思路一定是很清晰， 很简洁， 如果是混乱的， 很难做到不重不漏。
数位DP
难在状态， 需要通过题意抓住性质， 在优化你的状态。
动态DP
难在他就是难， 要用数据结构维护转移， 这样就可以实现修改， 所以叫动态DP， 综合性比较强。
DAGDP
不咋会
插头DP
不咋会
题目等我归纳一下。
标签：状态,乱讲,一般,背包,就是,转移,DP From： https://www.cnblogs.com/qerrj/p/18216537