最小成本的动态规划问题[关闭]

我有一个手机信号塔问题。有n个城镇。我们想在一些城镇建造手机信号塔。每个蜂窝塔都可以覆盖自己及其邻居。每个城镇都有建造手机信号塔的费用。我们想找出建造覆盖所有城镇的手机信号塔的最低成本。

例如，

(1)

城镇 1 2 3

成本 5 1 2 我们选择在town-2 建造手机信号塔。成本为1。

(2)

城镇 1 2 3 4

成本 5 1 2 3 我们选择在2/3镇建设手机信号塔。成本是1+2=3。

(3)

城镇 1 2 3 4

成本 5 1 3 2

我们选择在2/4镇建造手机信号塔。成本是1+2=3。

这是一种动态规划算法。我该如何解决？

谢谢 凌

我会选择以下几行：

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]}

这个想法是：

x是我们当前正在查看的城市数量，如果该城市已经被覆盖（被左侧的城市覆盖），则布尔值为 true。

• f(0,_)是一个空的基本子句 - 它可以自由地覆盖任何内容。
• f(1,false)是城市1未被覆盖的基地，所以你必须在那里放一座塔，并且f(1,true)是一个覆盖城市 1 的基地，所以你不需要塔，你就完成了。
• f(x,true)就是城市x已经被覆盖的情况，所以你可以在那里放一座塔，然后继续前往下一个城市[也被覆盖-f(x-1,true)】，或者不在那里放塔，下一个城市就不被覆盖了【f(x-1,false)]
• f(x,false)就是x城市没有被覆盖的情况，所以你基本上有两个选择，或者在里面放一个塔，然后继续f(x-1,true)。或者在下一个城市（x-1）放一座塔，然后继续f(x-2,true)

从...开始f(x,false), where x是最后一个城市，你会得到最小的解决方案。
不难看出，这个递归公式可以很容易地修改为DP。