我有个牢房塔的问题。有n个城镇我们想在一些城镇建牢房塔。每个细胞塔都可以覆盖自己和它的邻居每个城镇都有建造细胞塔的费用。我们想找出建造覆盖所有城镇的牢房塔的最低成本。
例如，
（一）
城镇1 2 3
花费5 1 2我们选择在2号镇建造细胞塔费用是1。
（二）
城镇1 2 3 4
花费5 1 2 3我们选择在2/3镇建造细胞塔。费用是1+2=3。
（三）
城镇1 2 3 4
费用5 1 3 2
我们选择在2/4镇建一座细胞塔费用是1+2=3。
有没有办法在O（n）时间内解决这个问题我看了dynamic programming proboem for minimum cost上的帖子，但我认为给出的答案是o（n^2）。我在动态编程中考虑过lis，但我认为它也会在o（n^2）中运行。
最佳答案
是的，有办法在o（n）中解决这个问题。在帖子中给出的答案具有线性时间复杂度，所以它正是你所需要的。