今天，我们要从记忆化搜索往正宗的动态规划过度，你准备好了吗？
树形DP最基本的特点是：需要处理的物品有依赖关系，而且依赖关系构成一棵树。 很容易可以发现，依赖关系树上的叶子节点是可以任意确定是否选取，而儿子节点的选择方案确定后，父亲的选择方案不会改变，而且能从儿子的状态来得到。
这么看来，树形DP的基本处理方法也显而易见了：进行深度优先搜索，先处理子问题，通过回溯再来处理父问题。我通过几道例题，来为大家讲解树形动规的基本问题模型和讨论（题目来源洛谷，侵删）
洛谷P2015
Problem
这道题是典型的树形DP的题目。
阅读题目我们发现，对于一个节点，有两种转移方法：1、剪掉这个节点与其父节点（根节点除外）相连的树枝；2、保留该树枝。 同时，对于一个节点，只有两个状态需要储存：1、当前节点的编号；2、当前节点和其儿子节点一共保留了多少条树枝。 通过分析，我们定义f[i][j]表示第i个节点及其儿子一共保留了j条树枝能保留的最多的苹果数量，动态转移方程如下：
动规方程
洛谷P1270
image
有了上一题的基础，这题的难度是不是减少很多了呢？
其实，这道题的难度主要在于对输入数据的处理【滑稽】。
这次，我们发现只有叶子节点有价值，而除根节点外所有节点都有费用（这里有一个小技巧，我们可以把边的费用推到子节点上，是不是也一样呢？），由于需要进入再离开，所以费用乘2即可。
和上一题一样，每个节点有两种转移方式：1、不走到这个节点；2、走到这个节点，并继续往下走。 同样，在每个节点有两个状态需要储存：1、当前节点编号；2、从当前节点往下走还剩多少时间。
试一试自己能否写出转移方程【加油】。
洛谷P1270
Problem
这道题好像依赖关系不是树啊，怎么办呢？
这时候，我们要找到题目中隐含的性质，并且对问题进行转化。 我们发现，每个其实只有一条出边，这条边看起来有向，但是其实是无向的（因为两个其实不能同时存在）。 这样，我们就得到了第一个性质：每一个连通块之中，最多只有一个环。 如果没有环，那就是一棵树，直接树形DP就行了，转移方程如下：
动规方程
那么，如果是一个环怎么办呢？
显然，一个环上相邻的两个节点一定有一个节点不选，那么我们任选环上相邻的两个节点，每次强制一个不选，然后把这条边切断，把不选的节点当根，跑一遍和上面一样的树形DP就行了。
以上就是树形DP的基本问题模型和套路，如果想要更加熟练的掌握这类DP的技巧，建议多刷刷题哦。
【信息学竞赛从入门到巅峰】，一个专注于分享OI/ACM常用算法及知识的公众号。
网友评论