树形动态规划

前言

上期文章，我们讲了区间动态规划的内容，如果对区间动态规划的内容还有疑问的话，可以参考我的上期内容，而这期我们就来讲解树形动态规划的内容，话不多说，我们直接开始。

一、树形动态规划是什么？

要搞清楚这个问题，我们首先要了解树这种数据结构，树是一种非线性数据结构，最上面的结点叫作树的根节点，而其后面所跟着的结点叫作根的子节点，同时其根结点也叫作父节点，树是一种一对多的数据结构，而树形动态规划就是利用如同树这种数据结构来解决相应的问题的动态规划，如果对树这种数据结构不了解的读者可以先去了解一下这种结构再来学习这篇文章。

二、对树形动态规划的分析

1.分析具体实例

我们以经典的问题没有上司的舞会为例，某大学有 n 个职员，编号为 1…n。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 r i，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。首先这种问题是一个典型的树形动态规划问题，了解动态规划的知道，求解动态规划问题的最重要的一步就是求出动态转移方程，那么这种问题很明显就是先确认当前的状态，由于当有上司在场时，其职员就一定不会来，而上司不再时职员可来，可不来，那么就需要记录职员的状态一确定是否来这个舞会。因此需要设置一个二维数组dp[MAX][2]来确定其状态，在此例中结合树这种数据结构，很容易想出，用父节点来代表其上司而用子节点来代表其直属的职员，我们用1代表这个人来的舞会，用0代表这个人不来舞会，用u代表上司，v代表其直属下属，即可推得状态转移方程为dp[u][1]+=dp[v[0],dp[u][0]+=max(dp[v][0],dp[v][0]),其中dp[j][0/1]代表这个人来舞会或者不来舞会所获得的快乐指数，当动态转移方程被推出时，问题就在于如何利用树形结构来求解最大快乐指数，在树这种数据结构中有两种遍历方法，一个叫作深度优先遍历，另一个叫作广度优先遍历，我们一深度优先遍历为例，如果不太了解这两种遍历的读者可以自行查询资料再来看这篇文章，其实对于树形动态规划而言，往往是使用深度优先遍历这种暴力法来求解问题，利用此种方法可以对问题进行求解，不过在此之前需要先构建好树这种数据结构，来方便我们使用深度优先遍历。构建树的方法随后会在下面的代码中给出，那么绕了这么大一圈，我们终于分析完了树形动态规划的问题。

2.树的构建过程以及最终的代码

此问题求解的代码如下：

#include<iostream>#include<algorithm>using namespace std;constintMAXN=6010;// 数据规模最大6000// 纯数组模拟邻接表（替代结构体）intto[MAXN];// to[i]表示第i条边指向的子节点intnext_edge[MAXN];// next_edge[i]表示第i条边的下一条边索引inthead[MAXN];// head[u]表示以u为父节点的第一条边的索引inthappy[MAXN];// 每个职员的快乐指数intdp[MAXN][2];// dp[u][0]不选u, dp[u][1]选ubool is_root[MAXN];// 标记是否是根节点intedge_cnt;// 边的计数器// 添加边：u是父节点，v是子节点voidadd_edge(intu,intv){to[edge_cnt]=v;// 第edge_cnt条边指向vnext_edge[edge_cnt]=head[u];// 指向上一条边head[u]=edge_cnt++;// 更新head[u]为当前边索引}// 深度优先搜索遍历树，计算dp值voiddfs(intu){// 初始化状态dp[u][1]=happy[u];// 选u，初始快乐值为自己dp[u][0]=0;// 不选u，初始快乐值为0// 链式遍历u的所有子节点（纯数组实现）for(inti=head[u];i!=-1;i=next_edge[i]){intv=to[i];// 获取当前边指向的子节点vdfs(v);// 递归处理子节点// 状态转移dp[u][1]+=dp[v][0];// 选u则子节点必不选dp[u][0]+=max(dp[v][0],dp[v][1]);// 不选u则子节点选/不选取最大}}intmain(){intn;cin>>n;// 初始化数组for(inti=1;i<=n;i++){head[i]=-1;// 初始无任何边is_root[i]=true;// 初始假设都是根节点}edge_cnt=0;// 边计数器清零// 输入快乐指数for(inti=1;i<=n;i++){cin>>happy[i];}// 输入上下级关系，构建树for(inti=0;i<n-1;i++){intl,k;cin>>l>>k;// k是l的直接上司add_edge(k,l);// 添加k到l的边（l是k的子节点）is_root[l]=false;// l有上司，不是根节点}// 找根节点（校长）introot=0;for(inti=1;i<=n;i++){if(is_root[i]){root=i;break;}}// 计算DP值dfs(root);// 输出最大值cout<<max(dp[root][0],dp[root][1])<<endl;return0;}# 总结 树形动态规划的问题主要是首先先求解出动态转移方程，然后再以此为核心，利用深度优先搜索构建出树这种数据结构，最后再进行求解。 最后如果文章有内容上的问题欢迎私信我指正，对此类讲解感兴趣的读者可以关注一下。 最后的最后感谢大家的观看，我们下期再见。