DP综合

DP（Dynamic Programming），又称动态规划，~~就是动态地进行规划~~。
正式定义：通过把复杂问题分解为简单的子问题来求解的方法，并不是指某种具体的算法。用来解决的问题具有 最优子结构，无后效性，重叠子问题 这三种特性。
个人理解：高级的递推，用已知解去更新未知解。也是区分蒟蒻和巨佬的重要手段。同时用途极广，和数学中的数列一样，可以结合其他知识点出很难的题。
关键步骤：

设计状态（将原问题分解为子问题）
推导状态转移方程
按顺序实现状态转移

状态转移实现：递推（循环）递归（记忆化搜索）
接下来介绍几种常见的模型。

线性 DP

最基础的一类 DP，线性的进行状态转移。

背包

经典 DP 模型。

引入（01背包）

$N$ 个物品，第 $i$ 个物品的重量 $w_i$，价值 $v_i$，以及背包总容量 $W$，最大化能取的物品的价值。
定义 $dp_{i,j}$ 为前 $i$ 个物品，占用了 $j$ 的容量的最大价值。转移方程：
$$dp_{i,j}=max{dp_{i-1,j-w_i}+v_i}$$

滚动数组空间优化

注意到 dp 数组的空间复杂度为 $O(NW)$，很大。又发现每次 $dp_i$ 只用 $dp_{i-1}$ 转移，可以直接把这一维度优化掉，但循环顺序要改变。

01背包

1
2
3

for(int i=1;i<=n;i++)//枚举物品 
    for(int j=W;j>=w[i];j--)//枚举体积
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

完全背包

1
2
3

for(int i=1;i<=n;i++)//枚举物品 
    for(int j=w[i];j<=W;j++)//枚举体积
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

树形DP 简介

顾名思义，就是在树上进行 DP。由于树的递归性质，通常的写法就是在 dfs 遍历树时进行状态转移。

通常，$dp_u$ 状态一般都为以 $u$ 为根的子树的最优解。先 dfs 遍历子树的所有最优解，然后向上传递给子树的父节点来转移，最终根节点的值即为所求的最优解（当然也有向下转移的）。

换根DP

上述的普通树形 DP 只能求解一个固定点为根，若是要枚举每一个根，岂不是得 $O(n^2)$ ？
非也非也，我们发现相邻的节点作为根，树除了他们俩本身基本不会有啥变化，因此换根的时候只有修改他俩的 DP 值就好了，复杂度 $O(n)$。就会有以下神板，只需推出一个转移式即可：

模板1

void dfs1(int u,int pre){
    for(int v:g[u])
        if(v!=pre) dfs1(v,u),/*v对u转移;*/;
}
void uv(int u,int v){
    //v对u还原 
    //u对v转移 
} 
void dfs2(int u,int pre){
    //此时dp[u]的值就是u作为根 
    for(int v:g[u])
        if(v!=pre) uv(u,v),dfs2(v,u),uv(v,u);
}