树形DP是以子树大小 / 深度为阶段的类线性DP。
最优结构：子树的信息保存在子树树根上。
状态转移：只发生父亲和儿子之间。
实现方式：
定义 \(f_{x,0}\) 和 \(f_{x,1}\) 为以 \(x\) 为根节点的子树，且 \(x\) 去 / 不去的最优解。
状态转移方程：
最终结果：\(\max(f_{rt,1},f_{rt,0})\)
首先加一个 \(0\) 号点作为所有没有先修课的公共祖先，最终结果是选择 \(m+1\) 门课程的最大学分。
定义 \(f_{x,i,t}\) 为以 \(x\) 为根的子树中，在 \(x\) 的前 \(i\) 个孩子中选 \(t\) 门课能够获得的最大学分。
状态转移方程：
其中 \(u\) 为 \(x\) 的第 \(i\) 个儿子，\(size(u)\) 为 \(u\) 的儿子个数。
我们发现 \(i\) 的转移中，\(size(u)\) 已经在前面的 \(dfs\) 中得到，所以 \(i\) 只会和 \(i-1\) 直接相关，与之前所学的背包十分相似，考虑利用背包的模型优化。
优化：像 \(01\) 背包一样，压掉上面定义中的第二维，倒序枚举 \(t\) 实现。
简要题意：
\(n\) 个点的无根树，每条边都有一个流量，令所有度数为 \(1\) 的点为汇点。
问令哪个点为源点时，流量最大，求出最大流量。
朴素做法：
对于每个点都执行一遍树形DP。
定义 \(f_x\) 为以 \(x\) 为根的子树中能获得的最大流量。
时间复杂度 \(O(n^2)\)
换根法：
首先对于任意一个节点 \(u\) 执行一遍树形DP。
对于 \(u\) 的一条出边 \(u→v\) ，当我们把根从 \(u\) 换到 \(v\) 时，考虑哪些情况会对答案产生影响。
对于环形的结构，我们有两种做法：
每天有 \(n\) 个小时，在第 \(i\) 小时休息能回复 \(w_i\) 点体力，每天要有相同的 \(k\) 个小时休息（可以不连续），但每次休息的第一个小时无法恢复体力。
问每天能回复的最大体力。
分析：
首先考虑线性结构下的DP（一天内的情况）
定义 \(f_{i,j,0/1}\) 表示前 \(i\) 个小时休息 \(j\) 个小时，并且第 \(i\) 个小时是否休息。
状态转移方程：
下面考虑环形结构：
在上述做法中我们断环为链处理了一遍，此时我们必须连接起来处理一遍，最后取 \(\max\) 即可。
具体做法：
令 \(f_{1,1,1}=w_1\) ，最后取 \(f_{n,k,1}\) 即可。
时间复杂度：\(O(n^2)\)
简要题意：
在一条环形公路上均匀分布 \(n\) 座仓库，仓库 \(i\) 和仓库 \(j\) 之间地距离定义为 \(dis_{i,j}=\min(|i-j|,n-|i-j|)\) ，仓库 \(i\) 存放有 \(a_i\) 的货物，在 \(i,j\) 两座仓库间运送货物需要 \(a_i+a_j+dis_{i,j}\) 的代价。
求在哪两座仓库中运送货物需要的代价最大。
分析：
考虑断环为链并复制一倍。
定义 \(f_{i,j}\) 为在长度为 \(2n\) 的链上 \(i,j\) 两座仓库运送货物的最大代价。
此时状态转移方程为：
显然，第一维枚举 \(i\) ，第二维枚举 \(j\) ，时间复杂度： \(O(n^2)\)
下面考虑优化：
不妨将其换个形式：
当 \(i\) 固定时，\(a_i+i\) 已经固定，接下来只需要考虑 \((a_j-j)\) 的最大值即可。
考虑对这一部分使用单调队列维护，此时就可以在 \(O(n)\) 的时间内得到结果
不满足“无后效性”：状态之间互相转移，互相影响，构成环形，无法确定出一个合适的DP阶段。
解决方法：
简要题意：
给定一张 \(n\times m\) 的棋盘，有一个机器人在 \((x,y)\) 位置，机器人每一步等概率地停在原地，向左一格，向右一格，向下一格，当然机器人不能离开棋盘。
求机器人从起点走到最后一行的任意一个位置上所需的期望移动次数。
分析：
定义 \(f_{i,j}\) 为从 \((i,j)\) 走到最后一行的期望次数。
状态转移方程：
建出矩阵为：
由于矩阵中每行不为 \(0\) 的个数很少，所以可以在 \(O(m)\) 的时间内消元。
时间复杂度：\(O(nm)\)
把一个集合的状态用二进制的 \(01\) 串代替转移。
适用于部分数据范围很小且难以单独转移的情况。
简要题意：
求把 \(n\times m\) 的棋盘分割成 \(1\times 2\) 的长方形的方案数。
分析：
等价于找到所有横放 \(1\times 2\) 的长方形的方案数，因为横放确定，竖放方案唯一。
定义 \(f_{i,j}\) 为第 \(i\) 列横放到第 \(i+1\) 列的状态为 \(j\) 的合法方案数。
状态转移方程：
其中 \(k\) 为枚举的上一行的状态，\(j\&k=0\) 表示这两行没有重叠，\(st_i\) 表示状态 \(i\) 中连续的 \(0\) 是否为偶数个（状态 \(i\) 是否合法）
对于 \(st_i\) 我们可以在 \(O(2^n)\) 时间内预处理。
对于第一维，可以使用滚动数组进行小优化。
时间复杂度：\(O(n\times 4^n)\)
原文：https://www.cnblogs.com/blueqwq/p/14864611.html