一些动态规划类型
树形 DP
树形 dp 的常用方法（例如树上背包）是将接下来要处理的儿子与以及处理完的儿子的全体进行合并，即把处理多个子树的问题转换为依次合并两个儿子的问题。
树形 dp 类型众多，故这里不多做赘述。
状压 DP
状压 dp 的核心是把状态用二进制数进行压缩（有些时候可能会用到四进制，如果一个点有三种或四种状态）。处理状压 dp 的核心是如何尽可能简洁地表示出当前状态，以及如何进行状态的转移。
例题：
这两题都是模板提，状态的表示比较容易，分别用 0/1 表示 无/有 即可。
这一题的难度则较大。对于每一个点看似有三个状态，但是三进制表示的状态数是过多的，我们需要想办法将其中两种状态合成一种状态进行表示，同时又做到不重不漏且可以转移。
数位 DP
数位 dp 是一类计数问题，形如统计区间 $[l,r]$ 内有多少数满足某条件。数位 dp 是有模板可用的，本质是利用了记忆化搜索的思想，核心是通过状态的设计使得可能的状态数尽可能，而状态如何设计与题目所要求的内容息息相关。
下面是数位 dp 的模板：
ll dfs(int pos,int status,bool flag){
//status 记录当前状态，根据题目来定，有时也需要用两个变量来记录
//flag 表示当前是否受到最大位限制（flag=1 -> 不受限）
if(pos==0) return 1;//这里表示遍历完后的返回值，根据题目变更
if(flag&&f[pos][status]!=-1) return f[pos][status];
int maxi=flag?9:a[pos];
ll ans=0;
for(int i=0;i<=maxi;i++){
ans=(ans+dfs(pos-1,,flag || (i<maxi)))%mod;//这里的状态转移要根据题目来写
}
if(flag) f[pos][status]=ans;
return ans;
}
//以下内容在主函数中使用
memset(f,-1,sizeof(f));
int cnt=0;
while(r){
a[++cnt]=r%10;
r/=10;
}
ll ans=dfs(cnt,,0);
cnt=0;
if(l!=0){
l--;
while(l){
a[++cnt]=l%10;
l/=10;
}
ans=(ans-dfs(cnt,,0)+mod)%mod;
}
例题：
概率 DP
概率 dp 的基础是求出概率或期望基于状态的转移方程。即，假定我们当前位于 $s$ 状态，接下来我们分别有 $p_1,p_2, \dots ,p_k$ 的可能性转移到 $t_1,t_2, \dots ,t_k$ 状态，那么我们就有 $f(s) = \sum p_i f(t_i)$，对于期望问题，式子也会变换为 $f(s) = \sum p_i(f(t_i)+b_i)$，其中 $b_i$ 为这一选择的消耗或收益。
然而，在列出式子之后，这些概率/期望的转移方程式可能会呈现出循环调用的情况，这时我们有两种方法解决。
- 当不同的式子所调用的函数个数是有限的（通常是一个）。例如这个被调用的状态是 $f(0)$，那我们可以将所有式子化成 $f(i)=A(i)f(0)+B(i)$，转而求出 $A(i),B(i)$ 即可。
- 高斯消元。
例题：
恶意竞争 基础题
筛子游戏 本题需要运用循环调用的解决方法
食堂 更复杂的一题
SOS DP（Sum over Subsets，子集和 DP/超集和 DP）
在子集和/超集和 dp 中，$F[sta]$ 表示所有 $sta$ 的子集/超集（含自身）的答案。
例如，二进制下 101 的子集为 101,100,001,000
二进制下 101 的超集为 101,111
然后用以下两种方法来进行状态方程的转移。
子集和
for(int i=0;i<(1<<bits);i++)//bits 为二进制下的位数
F[i]=A[i];//赋初值
for(int i=0;i<bits;i++)
for(int sta=(1<<bits)-1;sta>=0;sta--)
if(sta&(1<<i))
F[sta]+=F[sta^(1<<i)];//合并答案
超集和
for(int i=0;i<bits;i++)
for(int sta=(1<<bits)-1;sta>=0;sta--)
if(!(sta&(1<<i)))
F[sta]+=F[sta^(1<<i)];
评论