You don't need dynamic programming for this problem. Say you have an optimal solution, then look at the leaves of the tree. For each leaf, either it has a camera or its parent does, but not both (if neither have a camera, you could put a camera at that leaf and make the solution better). If its parent has a camera, you could take that camera away from the parent and put it at the leaf, and that would not make the solution any worse. This suggests that the following strategy is optimal:
T <-- initial tree ans <-- 0 Repeat while T has nodes Put a camera at every leaf ans <-- ans + # leaves of T Remove all leaves and their immediate parents from T return ans This can be implemented in linear time in the number of nodes, regardless of k. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
