动态规划求解高速公路广告牌问题时如何获取实际选中的广告牌位置

可以在求解最大收益的同时得到具体选中的广告牌位置，只需要在常规动态规划逻辑中新增路径记录数组，求解完成后通过回溯即可拿到完整的选中站点列表。

核心思路 #

常规的动态规划求解只会记录每个状态下的最大收益，我们只需要额外增加一个路径数组，记录每个状态最优解对应的决策（当前位置是否选广告牌、上一个选中的广告牌位置/下标），在状态转移更新最大收益的同时同步更新路径数组即可。

以下以两种常见的DP实现思路分别说明： #

方案1：按高速公路里程递推（对应通用实现逻辑） #

定义

• dp[i]：表示高速公路前i英里范围内能获得的最大收益
• path[i]：记录前i英里最优解的两个信息：当前i位置的广告牌是否被选中、若被选中上一个选中广告牌的最远有效位置（即max(0, i-最小间距)）对应的最优解末尾位置

状态转移逻辑

• 首先预处理所有候选站点，存入哈希表pos_revenue，key为站点位置，value为对应收益
• 从1到总长度M逐个里程遍历：
  • 若当前i位置没有候选广告牌：dp[i] = dp[i-1]，path[i]标记当前位置未选中，继承i-1的路径末尾
  • 若当前i位置有候选广告牌：
    • 计算两种选择的收益：不选当前广告牌的收益是dp[i-1]；选当前广告牌的收益是dp[max(0, i-d)] + pos_revenue[i]（d为最小间距）
    • 取两者较大值作为dp[i]：
      • 如果不选的收益更高：和无广告牌的处理逻辑一致
      • 如果选的收益更高：path[i]标记当前位置选中，记录上一个有效位置为max(0, i-d)

回溯拿结果

• 从i=M开始倒推
• 若当前path[i]标记为选中，就把i加入结果集，然后跳转到max(0, i-d)继续回溯
• 若未选中，就跳转到i-1继续回溯
• 直到i=0停止，最后把结果集反转就是按位置升序的选中站点列表

方案2：按候选站点递推（回溯逻辑更简洁） #

如果候选站点数量远小于高速公路总长度，这种方案的回溯逻辑非常直观，不需要逐里程倒推，只需要顺着prev数组跳转即可，适合站点稀疏的场景。

预处理

把所有候选站点按位置从小到大排序，得到排序后的位置数组pos[0..n-1]，对应收益数组rev[0..n-1]。

定义

• dp[k]：表示选第k个站点作为最后一个投放的广告牌时，能获得的最大收益
• prev[k]：表示得到dp[k]的最优解时，上一个被选中的站点下标，没有符合条件的前驱则存-1

状态转移逻辑示例代码

# 初始化
dp = [0]*n
prev = [-1]*n
max_total = 0
best_last_idx = 0

for k in range(n):
    # 初始值：只选当前第k个站点的收益
    dp[k] = rev[k]
    # 遍历所有k之前的站点j，找满足间距要求的最大dp[j]
    for j in range(k):
        if pos[k] - pos[j] >= d and dp[j] + rev[k] > dp[k]:
            dp[k] = dp[j] + rev[k]
            prev[k] = j
    # 更新全局最大收益和对应的最后一个站点下标
    if dp[k] > max_total:
        max_total = dp[k]
        best_last_idx = k

回溯拿结果示例代码

selected = []
cur = best_last_idx
while cur != -1:
    selected.append(pos[cur])
    cur = prev[cur]
# 反转得到升序的选中位置
selected.reverse()

内容的提问来源于stack exchange，提问作者Tony Miller