一、树型DP的概念
树型DP即在树上进行DP。
树是无环图，顺序可以是从叶子到根节点，也可以从根到叶子节点。
一般树型DP的特征很明显，即状态可以表示为树中的节点，每个节点的状态可以由其子节点状态转移而来（从叶子到根的顺序），或是由其父亲节点转移而来（从根到叶节点的顺序），也可是两者结合。
找出状态和状态转移方程仍然是树型DP的关键。
二、题目描述
树的最大独立集
对于一棵有N个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻（称为最大独立集）。
输入
第1行：1个整数N(1 <= N <= 6000)，表示树的结点个数，树中结点的编号从1..N
接下来N-1行，每行2个整数u，v，表示树中的一条边连接结点u和v
输出
第1行：1个整数，表示最大独立集的结点个数
样例输入
11
1 2
1 3
3 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
样例输出
7
三、分析
这道题用枚举是过不了的，因为数据范围太大了。
所以，我们决定使用树型DP。
那么，状态该怎么定义呢？
上面的概念说了，树上的每一个节点都是一个状态，那根节点的状态就可以由它的儿子的状态转移过来。
我们就定义一个数组f[6002][2];
f[i][0]表示以i节点为根的子树中，i
不选进
最大独立集时这颗子树中选进最大独立集节点个数。
f[i][1]表示以i节点为根的子树中，i
选进
最大独立集时这颗子树中选进最大独立集节点个数。
因为选出的节点不相邻，所以就可以得出状态转移方程
f[i][0]=sum(max(f[ch][0]+f[ch][1]));
//因为
它没有选进了独立集，所以要取它所有儿子的最优解
。
f[i][1]=sum(f[ch
][0]);
//因为它选进了独立集，所以它的儿子都不能选进独立集。
状态转移方程写好了，就剩下一些细节的处理。
1、初始化：如果i为叶子节点，则f[i][0]=0，f[i][1]=1。
2、确立树的结构：
root=1，dfs(root)。
bool vis[6002];
void dfs(int r)
{
if(r==0) return;
vis[r]=1;
for(int i=1;i<=n;i++){
if(rela[i][0]==r&&vis[rela[i][1]]==0){//如果父子关系相反，则反转父子关系。
int t=rela[i][0];
rela[i][0]=rela[i][1];
rela[i][1]=t;
}
}
for(int i=1;i<=n;i++)
if(rela[i][1]==r&&vis[rela[i][0]]==0)
dfs(rela[i][0]);
}
有了思路，代码实现就很简单了，注意要记忆化递归。
版权声明：本文为C20180602_csq原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。