I have an algorithmic problem in which I have a highway that is a straight line of length $n$ and a set of unique respective costs for construction of a radio tower for each mile on the highway. I am trying to use dynamic programming to find a way to minimize the cost of ensuring that each point in the highway is covered by at least one tower. I am given a length $n$ for the highway, an array of costs of length $n$ + 1, and must assume that the towers all will have a 5 mile range (eg a tower built at point $i$ will have range [$i$-5,$i$+5] inclusive).

I believe that my subproblem is OPT($i$) where $i$ is the minimum cost to cover the first $i$ miles of highway, however am having trouble constructing my recursive formula or algorithm. I know that a greedy approach would not be optimal in this case. I think that perhaps the shortest path problem could be harnessed however am having trouble creating an answer that follows the steps of dynamic programming. So far this is my algorithm:

  1. Initialize an array C of length $n$+1, where C[$i$] represents the minimum cost to cover the first $i$ miles of the highway.
  2. Set C[0] = 0 and C[1] = cost[1].
  3. For $i$ = 2 to $n$, calculate C[$i$] using the recurrence relation: C[$i$] = min(cost[$i$] + C[$i$-5], C[$i$-1])
  4. Return C[$n$], which represents the minimum cost to cover the entire highway.

Any advice would be appreciated!

  • 1
    $\begingroup$ I find SE to work best with an explicit, answerable question near the end of a question post. There's How do I ask a Good Question? $\endgroup$
    – greybeard
    Dec 1, 2023 at 11:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.