# Covering nodes in a tree

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.