algorithm - dynamic programming proboem for minimum cost -

i have cell tower question. there n towns. want build cell tower in of towns. each cell tower can cover , neighbor. each town has cost build cell tower. want find out minimum cost build cell tower cover towns.

for example,

(1)

town 1 2 3

cost 5 1 2 select build cell tower in town-2. cost 1.

(2)

town 1 2 3 4

cost 5 1 2 3 select build cell tower in town-2/3. cost 1+2=3.

(3)

town 1 2 3 4

cost 5 1 3 2

we select build cell tower in town-2/4. cost 1+2=3.

it's dynamic programming algorithm. how can solve it?

thanks ling

i'd go among following lines:

f(0,_) = 0 f(1,true) = 0 f(1,false) = cost[1] f(x,true) = min{ f(x-1,true) + cost[x], f(x-1,false) } f(x,false) = min { f(x-1,true) + cost[x], f(x-2,true) + cost[x-1]} 

the idea is:

x current number of city looking at, , boolean true if city covered (by city left).

• f(0,_) empty base clause - free cover nothing.
• f(1,false) base city 1 not covered, must put tower there, , f(1,true) base city 1 covered, don't need tower , done.
• f(x,true) case city x covered, can put there tower, , continue next city [which covered - f(x-1,true)], or don't put tower there, , next city not covered [f(x-1,false)]
• f(x,false) case city x not covered, have 2 choices, or put tower in there, , continue f(x-1,true). or put tower in next city (in x-1) , continue f(x-2,true)

start f(x,false), x last city, , you'll minimal solution.
it easy see recursive formula can modified dp.