c++ 不撞南墙不回头――树形动态规划(树规) - Easy sir - 博客园



拿到一道树规题,我们有以下3个步骤需要执行:

  1. 判断是否是一道树规题:即判断数据结构是否是一棵树,然后是否符合动态规划的要求。如果是,那么执行以下步骤,如果不是,那么换台。
  2. 建树:通过数据量和题目要求,选择合适的树的存储方式。如果节点数小于5000,那么我们可以用邻接矩阵存储,如果更大可以用邻接表来存储(注意边要开到2*n,因为是双向的。这是血与泪的教训)。如果是二叉树或者是需要多叉转二叉,那么我们可以用两个一维数组brother[],child[]来存储(这一点下面会仔细数的)。
  3. 写出树规方程:通过观察孩子和父亲之间的关系建立方程。我们通常认为,树规的写法有两种:

a.根到叶子: 不过这种动态规划在实际的问题中运用的不多。本文只有最后一题提到。

b.叶子到根: 既根的子节点传递有用的信息给根,完后根得出最优解的过程。这类的习题比较的多。

注意:这两种写法一般情况下是不能相互转化的。但是有时可以同时使用具体往后看。

 

以下即将分析的题目的目录及题目特点:

1、加分二叉树:区间动规+树的遍历;

2、二叉苹果树:二叉树上的动规;

3、最大利润:多叉树上的动规;

4、选课:多叉树转二叉;

5、选课(输出方案):多叉转二叉+记录路径;

6、软件安装:判断环+缩点+多叉转二叉;

【4、5、6属于依赖问题的变形】


Read full article from c++ 不撞南墙不回头――树形动态规划(树规) - Easy sir - 博客园


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts