树型动态规划 - NOCOW



树型动态规划

来自NOCOW
跳转到: 导航, 搜索

树型动态规划就是在"树"的数据结构上的动态规划,树型动态规划是建立在树上的,所以有二个方向: 1.根―>叶:这种题目基本上碰不到 2.叶->根:根的子节点传递有用的信息给根,完后根得出最优解的过程。这种的题目是树型动态规划的最常见类型。 首先定义

       无根树:题目中可以以任意节点为根建树,经过动态规划后即可直接得到最优值。        有根树:必须以某一个节点为根建树才能通过动态规划后得到最优值。 

基本上有这样一个步骤:

一、有根树:

      1.建树(一般以递归方式实现,有时数据过大以BFS方式实现) 
      2.在建树中找到叶子的时候特别赋值。 
      3.回溯时通过方程确定出每个节点的最优值并记录。 
      4.遍历完整棵树后一般以根节点值作为最终值。 


补充:关于建树,有很多时候会将原来的多叉树改造为左孩子右兄弟的二叉树,以下两道例题用到了这种改造。
例题1:Tyvj P1051 选课
例题2:Vijos P1518 河流(IOI2005 Rivers)
--澹台彦澍 02:08 2009年9月8日 (CST)
//简单的改造代码:         for i:=1 to n do             if ft[root[i]]=false then//这个节点目前还没有孩子                 begin                   a[root[i]].left:=i;//把这玩意儿放到当前节点的左边                     ft[root[i]]:=true;//标记-有孩子了                     num[root[i]]:=i;//该节点当前最后一个孩子                 end             else//有孩子了                 begin                   a[num[root[i]]].right:=i;//把这玩意儿给他当前最后一个孩子的右边                      num[root[i]]:=i;               end;//By 澹台彦澍


二、无根树:

      1.随机定根,重复有根树过程       2.要枚举节点作为根的情况重复有根树过程。 
例题:Vijos P1100 加分二叉树(NOIp2003第三题)

Read full article from 树型动态规划 - NOCOW


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