Part 1：DP 的本质
相信每个同学，都曾经有过被 DP 虐的经历。大部分同学在初学 DP 的时候，总是见一道题背过一道题，最后基本上是学会所有常见的套路，然后开始套模板。
然而，随着层次的提升，这种文科生的思维就不够用了——毕竟谁会在 IOI 上傻乎乎地出个石子合并或者是多重背包呢？
这样，我们就需要贴近 DP 的本质。
简单来说，DP 是一个打填表的过程。通常情况下，DP 的转移方程总是会涉及到一个数组，比如说这个：
是 01 背包的转移方程。实际上他就相当于是在填写一个表格，第 \(i\) 行 \(j\) 列的内容就是前 \(i\) 个物品不超过 \(j\) 的最大价值。这里是一个递推关系，也就是说我们需要通过之前的内容推导出来现在的内容。
Part 2：DP 的技巧
1.状态不够
比如说Vacation 。如果仅仅是最大值，那么我们也就无需搬出 DP 了。然而我们的题目给我们规定了一个非常可·爱的条件：
但他不能连续两天进行同一种活动
那么我们就需要加上一维“今天做的事情”。
2.状态过大
比如说Knapsack 2。这个题猛一看好像很简单，但是再一看呢？
$ 1\ \leq\ N\ \leq\ 100 $
$ \color{red}1\ \leq\ W\ \leq\ 10^9 $
$ 1\ \leq\ w_i\ \leq\ W $
$ 1\ \leq\ v_i\ \leq\ 10^3 $
然后呢？我们发现按照我们最开始的方法是无法通过这个题目的。因为这个特殊的数据范围，我们需要进行调换。
Part 3：刷表与填表
刷表法和填表法是两种各有优劣的方法。举个例子，斐波那契数列也可以算作是一个简单的 DP，那么我们就可以列出方程：
\[f_i=f_{i-1}+f_{i-2} \]那么这其实就是填表法，也就是说，枚举的是结果，也就是 \(f_i\)。简单而又明了，是不是每个人都是这么想的？
有同学可能就会问了：难道还有别的做法吗？这个不就很简单了吗？
然而你再看这个转移方程：
\[f_{i+1}=f_i+f_{i+1},f_{i+2}=f_i \]似乎也是正确的。这里我们其实是枚举每一个已知量，然后检查所有有关的量。对于这道题来说，填表法就足够的好用。然而对于一些你并不知道它的确切的“\(f_i\) 究竟是从哪里来的”的题目而言，这种做法就显得十分有价值。另外，填表法在有些地方会产生巨大的时间复杂度，这个时候刷表法的价值就体现出来了。
标签：方程,填表,笔记,学习,leq,Part,我们,DP From： https://www.cnblogs.com/liyuanzhuo6811/p/18062964