Question:
Given a tree representing a neighbourhood where each node is a house. Assign an antenna to each node such that the whole tree is covered.
An antenna of strength 0 can only provide a signal to itself. An antenna of strength j can provide a signal to itself and nodes that are j steps away from it. The cost of building an antenna at a house is given by a cost function f(ni, j) where ni is the i'th node and j is the signal strength. Additionally the cost of an antenna with strength j has to be less or equal the cost of an antenna with strength i if j is weaker than i.
7
|
6
/ | \
3 4 5
/ \
1 2
For example an optimal solution in this tree for a cost function f(ni, j) = j + 1 would be to place an antenna of strength 2 at node 6.
This is a school assignment and the ultimate goal is to write a dynamic programm that can solve it in O(n^2). As far as my understanding goes the 'trick' of dynamic programming is to find a recursive algorithm that can solve the problem in exp. time and then use a table to cache the intermediate answers that build upon each other to improve the time complexity.
I fail in seeing a recurrence in the problem and and would appreciate if someone could point me in the right direction.