前言
某人云：“图样图森破，上台拿衣服。”
如题所见，这是一篇DP复习博客。本文旨在帮助我恢复我并不存在的动态规划姿势水平。由于dp的核心不在实现，所以内容停留在子状态的设计以及优化上。
另外，我琢磨了一下，取这么个名字应该不会有重名。。。应该不会吧？
背包dp
某人云：“闷声发大财，才是坠吼的。”
01背包
给定一个大小为W的背包，以及若干件物品。每个物品都有两个属性：大小\(w_i\)与价值\(p_i\)。今有某人，求问一种搭配，使其总价值不知道比你高到哪里去，而总大小不超过背包大小。当然，某人作为一个老者，并不需要知道具体的搭配，只需要知道最大大小几何。
考虑最简单的想法，设子状态为\(f[i][j]\)，表示当前背包中已有重量为j的物品，而你于第i个物品前举棋不定。那么不难想到，在这种情况下，状态转移方程为$$f[i][j+w_i]=max{f[i][j+w_i],f[i-1][j]+p_i}$$ 我们无需考虑不取的情况，这个结论是平凡的。因此可以稍微改进这个dp。重新令子状态\(f[i][j]\)表示你决定选择第i个物品，而选择之后背包里物品总重量为j，如此状态转移方程应为$$f[i][j]=max{f[i][j],f[i-1][j-w_i]+p_i}$$
不难看出，这个算法的空间复杂度是\(O(NW)\)的，但由于每一层子状态只依赖于上一层的子状态，而这种依赖是具有方向性的（即在第二维上单调）。因此我们可以省去第一维。注意这样的话枚举顺序需要保证不会出现覆盖。
完全背包
某人拥有无穷无尽的time_energy，因此虵无限制地复制了所有物品，并求问同样的问题。
这个问题本质上和前一个问题是一样的，只不过我们每一次不一定是取一件物品，应此需要枚举取多少件物品。建立在上一个算法上的朴素思想其时间复杂度是极高的（我们凭空多枚举了一维）。这里可以想到一个不是很显然的优化：将01背包第二维的枚举由逆序改为顺序。01背包之所以是逆序枚举，是因为顺序枚举会导致当前层状态被覆盖，相当于反复取用。但是完全背包中物品的数量是无限的，因此顺序枚举恰好可以满足其需求。
多重背包
某人是曾经的ff0000_w0r1d力量拥有者，所以虵对所有物品的取用上限做了限制，并求问同样的问题。
现在物品的选用不再是无限的，那么我们可以考虑把某种物品看成若干个同样的物品，于是乎可以套用01背包的模型。但是这样十分容易导致物品拆分过多，因此可以想到将物品数量二进制拆分。其性质保证可以再拆分数量最少的前提下拼凑出所有选用组合。
数位dp
某人云：“听风就是雨，将来负责任。”
相较其他种类的动态规划，数位dp的特征及其明显，包括但不限于：电话号码与巨大的数据范围。
Luogu P2657 [SCOI2009] windy 数
上题是一道经典的数位dp题，可以设子状态为\(f[i][j]\)，表示当前枚举到第i位，上一位的值为j。然后可以刷表或是记忆化搜索解决本题。数位dp比较套路，题目大同小异，至多就是增加多一点限制条件。数位dp的实现上需要注意一些边界问题。
区间dp
某人oasdfoiasjfdoihasdufausidhfas
Luogu P1880 [NOI1995]石子合并
区间dp也有着不低的套路性，考虑子状态\(f[i][j]\)，表示区间\([i,j]\)上的答案。毋庸置疑，较大区间的答案依赖于较小区间的答案。事实上，区间之间的依赖关系是单调连续的。也就是说，可以通过\(f[i-1][j],f[i][j-1]\)的值推出\(f[i][j]\)的值。具体细节不做赘述，但是思路是明朗的。区间dp的实现上同样需要注意边界问题。
树形dp
某人云：“沟里郭嘉身似椅，骑营火赴必取之。”
树形dp，顾明思义，即为树形的dp，这样的dp通常都存在依赖关系，譬如下题。
P2014 [CTSC1997]选课