动态规划求解公路最小成本信号塔部署问题咨询

问题分析 #

你的子问题定义OPT(i)为覆盖前i英里公路的最小成本是合理的，但当前的递推公式存在逻辑漏洞：

• C[i-1]仅保证覆盖前i-1英里，但i英里的位置可能未被覆盖（比如前i-1英里的最后一座信号塔建在i-6，其覆盖范围仅到i-1），因此直接取min(cost[i]+C[i-5], C[i-1])无法确保i英里被覆盖。
• 信号塔的覆盖范围是[k-5, k+5]，要覆盖i英里，最后一座信号塔的位置k必须满足k >= i-5（否则k+5 < i，无法覆盖i），这一点在你的递推中没有充分考虑。

正确的动态规划方案 #

子问题重新明确

OPT(i)：覆盖**0到i英里（含两端）**所有位置的最小成本。

递推公式

对于每个i（从0到n）：

• 当i < 0时，OPT(i) = 0（无需覆盖任何区域）；
• 当i >= 0时，OPT(i) = min{ cost[k] + OPT(max(k-5, -1)) | k ∈ [max(0, i-5), i] }

解释：

• 我们需要枚举所有能覆盖i英里的信号塔位置k：k的范围是max(0, i-5)到i（k不能小于0，且k+5 >= i）；
• 当在k位置建信号塔时，它会覆盖[k-5, k+5]，因此只需要保证0到k-5的区域已被覆盖（即OPT(k-5)），加上当前信号塔的成本cost[k]；
• 取所有可能k对应的成本最小值，即为OPT(i)。

修正后的算法步骤 #

1. 初始化长度为n+1的数组OPT，其中OPT[i]表示覆盖0到i英里的最小成本；
2. 处理边界情况：虚拟边界OPT[-1] = 0（代码中通过条件判断处理）；
3. 对于i从0到n：
   • 确定k的起始位置：start_k = max(0, i-5)；
   • 遍历k从start_k到i，计算current_cost = cost[k] + (OPT[k-5] if k-5 >=0 else 0)；
   • OPT[i] = min所有current_cost；
4. 返回OPT[n]。

示例验证 #

假设n=6，cost数组为[10, 2, 3, 4, 5, 6, 7]（索引0到6对应位置0到6）：

• OPT[0] = min(cost[0]) =10；
• OPT[1] = min(cost[0], cost[1]) =2；
• OPT[2] = min(cost[0], cost[1], cost[2]) =2；
• OPT[3] = min(cost[0], cost[1], cost[2], cost[3]) =2；
• OPT[4] = min(cost[0], cost[1], cost[2], cost[3], cost[4]) =2；
• OPT[5] = min(cost[0], cost[1], cost[2], cost[3], cost[4], cost[5]) =2；
• OPT[6] = min(cost[1], cost[2], cost[3], cost[4], cost[5], cost[6]+OPT[1]) = min(2,3,4,5,6,7+2)=2，正确，因为建在位置1的信号塔覆盖[-4,6]，完全覆盖0-6，成本仅为2。

代码示例（Python） #

def min_tower_cost(n, cost):
    opt = [0]*(n+1)
    for i in range(n+1):
        start_k = max(0, i-5)
        min_cost = float('inf')
        for k in range(start_k, i+1):
            prev = opt[k-5] if k-5 >=0 else 0
            current = cost[k] + prev
            if current < min_cost:
                min_cost = current
        opt[i] = min_cost
    return opt[n]

内容的提问来源于stack exchange，提问作者Izzy Handkammer