FineLine's blog

A Problem on DP on Trees

By FineLine, history, 8 years ago, In English

Hello Everyone ,I am trying to solve this problem for some time now.I could not find an explanation in English for it anywhere . The question is related to DP (on trees) . In Brief the problem asks you to find the minimum number of edges to be removed to isolate a subtree of size p .The original problem statement can be seen here.Thanks in advance :)

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

Comments Comments (6)
| Write comment?
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I think it is a dp[v][sz] with knapsack-like recalc

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

A similar problem Barricades appeared in Algorithmic Engagements 2007. That has been discussed in the book Looking For A Challenge, the preview of which includes this problem. :)

→ Reply