NeverSayNever's blog

Dynammic Programming on Tree
By NeverSayNever, 9 years ago, In English

Hello friends ,

I have decided to learn some new stuff in my mid semester break. So, it will be great if some of you can share some problems related to dynamic programming on tree. Although i am not much familiar with this topic so i want some useful links to learn the tricks involved in dynamic programming on tree .

Looking forward for your comments.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I like this one. This is a nice one too. I hope you'll enjoy them. Please, share those you have found because I like problems that can be solved using DP on tree. :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks P_Nyagolov but it will be great if you can provide some good source for learning dp on trees.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm, I can't provide such link because I never read about it. I think that DP on tree is just a DP. As you know what DP is, I think that the only thing that can improve your abilities is just solving a lot of problems and asking for help on those which you can't solve. So.. in my opinion what you need is problems, and I gave you some yesterday :)

      → Reply
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

This one is relatively easy. And you may try this one, if you want something more complicated)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks PI_love_Tanya_Romanova but it will be great if you can provide some good source for learning dp on trees.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      One more simple DP on a tree from recent contest. I agree with P_Nyagolov — DP on a tree isn't something special, just as any other DP — practice is a key to improving :) You may look in Google for something like dynamic programming on a tree to find some basic problems, but tutorials don't sound like a best idea for me.

      → Reply
»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

http://main.edu.pl/en/archive/pa/2007/bar

You'll firstly have to find an O(n ^ 3), which is pretty instructive, then, by a small trick, you can reduce it to O(n ^ 2).

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can Some please list down a few resources from where i can learn about DP on Trees.

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

https://www.hackerrank.com/challenges/tree-pruning

Nice problem for beginners like me. :)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For learning dp on trees, check this or this ... i learnt it from these links :)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

IOI 2005 Rivers is nice.
And IOI 2007 Training is something very hard.

→ Reply