Unable to Solve Dynamic Programming

Question

I had an assignment on dynamic programming due last night, but I had to turn it in unfinished because i could not understand how to solve the last problem:

The state wants to monitor traffic on a highway n miles long. It costs c_i to install a monitoring device on mile i of the highway. The maximum distance between monitoring devices should not be more than d miles. That is, if there is a monitoring device on mile i, then there must be one monitoring device from mile i + 1 to mile i + d (or it is the case that i + d > n). The state wants a plan that will minimize the cost. Assume there is an array C[1..n] of costs.

Let v_k be the cost of the best solution assuming a k mile highway and assuming a monitoring device on mile k. Given C and d, if the values of v₁ through v_k-1 are known, show how to determine the value of v_k. You can write this mathematically, or provide pseudocode in the style of the book. Note you need to take into account all possible values of k from k = 1 to k = n.

I'm sure a problem similar to this will appear on the exam coming up and I'd like to at least know where to begin solving this, so any assistance is appreciated.

Answer 1

With any dynamic programming problem. The trick is realizing where you can condense a lot of possibilities into a fewer number of possibilities.

A brute-force approach to this problem would be to try every possible location for the monitoring devices, eliminate those possibilities which are illegal (distance is greater than d), and then find the one with the minimum cost.

To go from brute-force to dynamic programming, you have to find where a lot of possibilities are equivalent. You can do this if you realize that you don't have to know the details of where the monitoring stations are before any particular location, all you need to know is the minimum cost to get there. Based on this, you can start with the simplest case and work from there.

Starting with k=1. What is the cost? This one is easy because we know we have to put a device at location 1, and there aren't any previous locations, so v[1] = C[1].

What about k=2? If d=1, then we had to have a device at location 1, so the cost is v[1]+C[2]. If d=2, then we also have the possibility of not needing a device at a previous location, so the cost is just C[2]. We'll choose the possibility with the least cost that is valid and call this v[2].

What about k=3? Now we have to consider v[2]+C[3], v[1]+C[3], or just C[3]. Again, we choose the one with the least cost that is valid and call it v[3].

We can proceed in the same way until we reach location n.