Following scenario:

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.