拿到一道树规题，我们有以下3个步骤需要执行：
- 判断是否是一道树规题：即判断数据结构是否是一棵树，然后是否符合动态规划的要求。如果是，那么执行以下步骤，如果不是，那么换台。
- 建树：通过数据量和题目要求，选择合适的树的存储方式。如果节点数小于5000，那么我们可以用邻接矩阵存储，如果更大可以用邻接表来存储(注意边要开到2*n，因为是双向的。这是血与泪的教训)。如果是二叉树或者是需要多叉转二叉，那么我们可以用两个一维数组brother[]，child[]来存储（这一点下面会仔细数的）。
- 写出树规方程：通过观察孩子和父亲之间的关系建立方程。我们通常认为，树规的写法有两种：
a.根到叶子: 不过这种动态规划在实际的问题中运用的不多。本文只有最后一题提到。
b.叶子到根: 既根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题比较的多。
注意：这两种写法一般情况下是不能相互转化的。但是有时可以同时使用具体往后看。
以下即将分析的题目的目录及题目特点：
1、加分二叉树：区间动规+树的遍历；
2、二叉苹果树：二叉树上的动规；
3、最大利润：多叉树上的动规；
4、选课：多叉树转二叉；
5、选课（输出方案）：多叉转二叉+记录路径；
6、软件安装：判断环+缩点+多叉转二叉；
【4、5、6属于依赖问题的变形】
Read full article from c++ 不撞南墙不回头――树形动态规划(树规) - Easy sir - 博客园
No comments:
Post a Comment