algorithm - 使用动态规划的最低成本

Question

我有一个手机信号塔问题。有n个城镇。我们想在一些城镇 build 手机信号塔。每个手机信号塔都可以覆盖自己和它的邻居。每个城镇都有 build 手机信号塔的成本。我们想找出 build 覆盖所有城镇的手机信号塔的最低成本。

例如，

(1)

城镇 1 2 3

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

(2)

城镇 1 2 3 4

COST 5 1 2 3 我们选择在 town-2/3 build 手机信号塔。成本是1+2=3。

(3)

城镇 1 2 3 4

费用 5 1 3 2

我们选择在 town-2/4 build 手机信号塔。成本是1+2=3。 有没有办法在 O(n) 时间内解决这个问题？我查看了 dynamic programming proboem for minimum cost 上的帖子但我认为给出的答案是 O(n^2)。我考虑过动态规划中的 LIS，但我认为它也会在 O(n^2) 中运行。

Answer 1

是的，有办法在 O(n) 内解决这个问题。帖子中给出的答案具有线性时间复杂度，因此它正是您所需要的。