Optimization for dp on tree needed.

Revision en1, by negativez2, 2019-09-19 10:29:26

Statement:

Given a tree of N nodes, every node i have a value A[i].

You have to find the maximum value you can get by picking a subtree (a subgraph of the tree which is also a tree) of exactly K nodes.

Constrain : 1 <= K,N <= 1000

This can be solve in O(n^3) by a simple dp, but after spending time thinking, I couldnt find a better solution. Can anyone solve this in O(n^2) ?

Help is appreciated.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English negativez2 2019-09-19 10:29:26 451 Initial revision (published)