我有一个算法问题，其中我有一条长度为 n 的直线的高速公路，以及在高速公路上每英里建造无线电塔的一组独特的各自成本。我正在尝试使用动态规划来找到一种方法来最小化确保高速公路上每个点都被至少一个塔覆盖的成本。 给定高速公路的长度 n，以及长度为 n + 1 的成本数组，并且必须假设所有塔楼的范围均为 5 英里（例如，在 i 点建造的塔楼的范围为 [i-5,i +5] 包括）。
我相信我的子问题是 OPT(i)，其中 i 是覆盖前 i 英里高速公路的最低成本，但是在构建我的递归公式或算法时遇到了困难。我知道在这种情况下贪婪的方法并不是最佳的。 我认为也许可以利用最短路径问题，但是我无法创建遵循动态规划步骤的答案。 到目前为止，这是我的算法：
假设在单元格 i 中放置一个塔是有效的，如果它与之前放置的所有塔一起覆盖了所有单元格 <= i+5. Since the range within 5 is covered by the tower at i, we can place a tower there if every cell from 0 up to i-6 is covered.
在 DP 数组中，单元格 i 中的值是在单元格 i 中有效放置塔的最小总成本。
然后，DP[i] = C[i] + min(DP[i-j]) 为 1 <= j <= 6. Treat the values of negative indices as being 0.
最后，答案是覆盖最后一个单元格的所有 i 的 DP[i] 的最小值。
覆盖第 i 个单元格的塔可以放置在 i-5 和 i+5 之间 11 个位置中的任意一个位置。
我将举一个较小的例子——相同的概念，但每个塔覆盖 2 以内的单元格。
输入：[16,4,8,12,7,5,11,12,14,3]
我们填写DP数组如下：
index: value & reasoning
0: 16 + min( 0, 0, 0)
1: 4 + min( 0, 0, 16) = 4
2: 8 + min( 0, 16, 4) = 8
3: 12 + min(16, 4, 8) = 12 + 4 = 16
4: 7 + min( 4, 8, 16) = 7 + 4 = 11
5: 5 + min( 8, 16, 11) = 5 + 8 = 13
6: 11 + min(16, 11, 13) = 11 + 11 = 22
7: 12 + min(11, 13, 22) = 12 + 11 = 23
8: 14 + min(13, 22, 23) = 14 + 13 = 27
9: 3 + min(22, 23, 27) = 3 + 22 = 25
最后 3 个中的任何一个都覆盖了最后一个位置，所以答案是 min(23, 27, 25) = 23。
通过跟踪每次选择的分钟数，我们可以找到为我们提供分钟数的塔的选择。
index 7: min comes from index 4
index 4: min comes from index 1
index 1: min comes from a negative index so we're done
23 来自索引 1, 4, 7
[16,(4),8,12,(7),5,11,(12),14,3]
在这个随机生成的示例中，答案恰好是均匀分布的，但并不总是如此。