【算法?日更?第九期】树型动态规划详解：二叉苹果树

2022-08-20 13:00:22

▎前置技能：动态规划&树

　　树型动态规划一听就知道是在树结构上使用的动态规划，那么不会树结构和动态规划怎么行？戳这里了解动态规划和树。

▎什么是树型动态规划？

?『定义』

　　树形动态规划问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。（copy自百度）

　　猜你也不愿意看，简单说就是掺了树的动态规划呗，也特别不到哪里去，只要树结构掌握的不错就行了。

?『为什么有树型动态规划，而没听说过图型动态规划、队列型动态规划什么的呢？』

　　这个很容易理解，因为树这个数据结构很特殊，只有一个前驱，有多个后继，本就是一个纯天然的递归结构，而动态规划常用什么方法呢？数组递推和记忆化搜索，巧了！记忆化搜索正是递归的方式，这同时也暗示着一件事：树型动态规划是不能使用数组递推的！要用记忆化搜索。

?『树型动态规划的方向』

　　①由叶到根：也就是从叶子结点（递归边界）向根节点（原问题）不断返回，最终在根节点（原问题）处得到答案。这种树型动态规划的方向很常见，也是我们平时使用递归时的方式。

　　②由根到叶：这种题目很不常见，主要就是将所有点当做一次根节点进行求值，然后有父节点向子节点转移信息。

?『树型动态规划的顺序』

　　树型动态规划可以理解为后序遍历，也就是先处理好子节点，再返回处理父节点。

▎树型动态规划的解题技巧

?『树型动态规划的一般步骤』

　　①建树：树型动态规划叫个这名字，总得有树吧，所以，一定要先建树，建树时要注意恰当的存储方式，数据规模较小时使用邻接矩阵，较大时使用邻接表，至于指针大佬就请默默走开。

　　②设计状态：动态规划怎么也得有状态了吧，一般树型动态规划通常是1~2维，所以时间复杂度一般不高，不过只有状态设计好了，才能正常的进行后续流程。

　　③状态转移方程：这是令人最讨厌的东西，纯找规律，要找到父节点和子节点之间的关系，才能写出来。

　　④确定答案：有些题目的答案需要推理一下，不过很多不需要，这也和状态的设计有关。

?『怎么判断题目是否适用于树型动态规划』

　　①长得就是树型动态规划题，比如后面的二叉苹果树那道题；

　　②先判断是否是动态规划，是否符合动态规划的三大性质；

　　③是否需要树；

▎实战演练

　　提起一棵苹果树，你会想到什么？

　　砸到牛顿头上的那个苹果？

　　被乔布斯啃了一口的苹果？

　　这可苹果树上可不一般，这是我见过的最奇葩的树。

　　废话不多说，直接上题：

1575：【例 1】二叉苹果树

时间限制: 1000 ms 内存限制: 524288 KB
提交数: 175 通过数: 104

【题目描述】

有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共 $N$

我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。

【输入】

第一行两个数 $N$

接下来 $N - 1$

【输出】

输出仅一行，表示最多能留住的苹果的数量。

【输入样例】

【输出样例】

【提示】

数据范围与提示：

对于 100% 的数据， $1 \leq Q \leq N \leq 100, N \neq 1$

【来源】

无

　　这道题一看就知道是树型动态规划，因为这分明就是一道树型动态规划题，那么怎么做呢？

Part one 建树

　　假设每行输入分别对应的变量是a，b，c。

　　先来考虑建树，建树都是应该递归建的，请看一下别人博客，一般都是这样的。小编的建树方式不太一样，那就是一直判断，如果b没有父节点，那么那么b就是a的子节点，存起来；如果b有父节点，那么a就是b的子节点，存起来。

　　那么左右子树呢？顺序没有任何关系，所以先存左子树，后存右子树，代码比较简单，就不过多解释了：

 1 cin>>n>>q;
 2     for(int i=1;i<=n-1;i++)
 3     {
 4         cin>>a>>b>>c;
 5         if(father[b]!=0) 
 6         {
 7             father[a]=b;
 8             if(leftchild[b]==0) leftchild[b]=a;
 9             else rightchild[b]=a;
10         }
11         else 
12         {
13             father[b]=a;
14             if(leftchild[a]==0) leftchild[a]=b;
15             else rightchild[a]=b;
16         }
17         apple[a][b]=c;
18         apple[b][a]=c;
19     }

Part two 设计状态

　　我们是要求以根节点保留q条枝条能保留的最多苹果数。那么不妨将f[i][j]表示为以i为根节点保留j条枝条能保留的最多苹果数。

Part three 状态转移方程

　　那么现在来考虑一件事，我们需要向左右两边分一些枝条量，各是k-1和j-k-1个（假设左子树有k个），为什么都减一呢？小编在调试代码的过程中发现：如果不减一，那么左右两边都会多分一个枝条，原因是转移时忘了转移的节点和原节点间有一个枝条。

　　所以方程是这样的f[i][j]=max{f[leftchild[i]][k-1]+f[rightchild[i]][j-k-1]+apple[i][leftchild[i]]+apple[i][rightchild[i]]}，同时要记得先特判k=0和k=j的情况，小编稍微改了改，就是这个熊样：

 1 for(int k=0;k<=j;k++)
 2     {
 3         int l=dp(leftchild[i],k-1);
 4         int r=dp(rightchild[i],j-k-1);
 5         if(k==0) x=r+apple[i][rightchild[i]];
 6         else if(k==j) x=l+apple[i][leftchild[i]];
 7         else x=l+r+apple[i][leftchild[i]]+apple[i][rightchild[i]];
 8         if(x>f[i][j])
 9         f[i][j]=x;
10     }

Part four 确定答案

　　小编可能设计的状态不太和别人一样，看见别人的博客答案和我的不一样，还有设计三维的，别人的答案：f[1][q+1]；小编的答案：f[1][q]。

Part five 一点忠告

　　小编是这样过的这道题的：

　　猜猜小编是怎么错的?小编显示忘了删测试代码和记忆化，一直以为哪里有不可告人的错误，结果被忘了删测试代码纠结了很长时间。

　　好了，代码如下：

 1 #include<iostream>
 2 using namespace std;
 3 int leftchild[1000]={0},rightchild[1000]={0},father[1000],apple[1000][1000],f[1000][1000],n,q,a,b,c;
 4 int dp(int i,int j)
 5 {
 6     if(j<=0) return 0;//边界条件必须考虑周全 
 7     if(leftchild[i]==0) return 0;
 8     if(f[i][j]) return f[i][j];//记忆化 
 9     if(j==1) //只剩1根枝条，那么肯定是选那根苹果多的呗 
10     {
11         return max(apple[i][leftchild[i]],apple[i][rightchild[i]]);
12     }
13     int maxn=-1,x;
14     for(int k=0;k<=j;k++)
15     {
16         int l=dp(leftchild[i],k-1);
17         int r=dp(rightchild[i],j-k-1);
18         if(k==0) x=r+apple[i][rightchild[i]];
19         else if(k==j) x=l+apple[i][leftchild[i]];
20         else x=l+r+apple[i][leftchild[i]]+apple[i][rightchild[i]];
21         if(x>f[i][j])//因为两边各分多少枝条数量不确定，所以依次模拟选最优的方案 
22         f[i][j]=x;
23     }
24     return f[i][j];
25 }
26 int main()
27 {
28     cin>>n>>q;
29     for(int i=1;i<=n-1;i++)//建树 
30     {
31         cin>>a>>b>>c;
32         if(father[b]!=0) 
33         {
34             father[a]=b;
35             if(leftchild[b]==0) leftchild[b]=a;
36             else rightchild[b]=a;
37         }
38         else 
39         {
40             father[b]=a;
41             if(leftchild[a]==0) leftchild[a]=b;
42             else rightchild[a]=b;
43         }
44         apple[a][b]=c;
45         apple[b][a]=c;
46     }
47     cout<<dp(1,q);
48     return 0;
49 }