I have a neighbourhood represented as a tree where each node is a house and I want to cover the whole neighbourhood with a signal.
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 while the cost of building a an antenna of strength i has to be less than or equal to building an antenna of strenth j, if i is weaker than j.
g | f / | \ c d e / \ a b
For example an optimal solution in this tree for a cost function
f(i) = i + 1
where i is the strength of the antenna, would be to place an antenna of strength 2 at node f.
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.
My problem is that I fail to see a recursion in the problem and can’t seem to make any progress why I would appreciate if someone could point me in the right direction.