树形DP状态表示： 树形DP的状态集合有两个f[u, 0]和f[u, 1]，分别表示所有从以u为根的子树中选择，且不选u这个点的方案，和选这个点的方案。 首先对于f[u, 0]，因为它没有选择u这个点，因此子节点自由选择，可以由f[j ,

状态压缩DP状态压缩本质上就是用一个二进制数来表示出所有的状态，从而方便用位运算节省速度。 蒙德里安的梦想要找到所有的方案数，我们需要找到所有横放1x2方格的合法方案数，当横放数量确定后，竖放的方格只需插入即可。 状态表示：用f[i] [j

记忆化搜索记忆化搜索有点像搜索+初始化判断，通过保存过去的结果，可以避免重复的搜索，以此达到更快的时间。 f[a] [b]表示走到a，b这一点的最大距离，因此f[a] [b]如果不为初始化的值，则一定是最大值，我们不必再重复搜索 #incl

数位DP感觉是一种出现很多次的题然而我一次都不会（（ 数位DP的核心是分情况讨论，找到一个第j位，表示第j位上数字i出现了多少次，最后将每个位数上数字i的出现次数相加即是总和。 对于一个数abcdefg，假定第j位是d，那么有如下可能： （

背包问题背包问题是一类很大的问题，很多问题都能转化成背包问题。 01背包01背包问题的特点是所有物品仅能用一次 状态转移方程 f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); 二维版

计数类DP整数划分可看作是完全背包问题的改版，将1~n的数看作体积，每个物品使用无限次，恰好能装满背包体积n的总方案数。 注意初始化时，我们要求的与完全背包不同，完全背包要求最大的价值，该题要求最大的方案数，因此我们至少有一种方案，应该全部

区间DP区间DP的核心是每次都将左边一堆与右边连续的一堆合并 状态表示：f[i] [j]表示将i到j合并为一堆的方案的集合的最小值。 状态计算： f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] +