我在高速公路上有一组 n 个服务站 D[]，这样 D[i] 就是车站的距离i 从高速公路开始。
我还有一系列成本 C[]，这样 C[i] 就是我的车辆在 i 站维修的成本>.
我的车必须在第一个站点进行维修，并且我的车辆最多可以在站点之间行驶 100 英里。
以最少的成本从高速公路的起点到达终点的最有效算法是什么(我需要知道在哪些车站停靠)？我能够找到一个最小化停止次数的贪心解决方案，但为了成本最低，我正在考虑 DP，具有最优子问题:
bestcost[j] = min( 0<i<j bestcost[i] + C[j] s.t. D[j]-D[i] <= 100)
并且有一个单独的数组last[j]，其中包含最后一个停靠站，这将是上述子问题中最好的i。
这是正确的方法，还是有更好的 Greedy/DP 解决方案？
最佳答案
递归最好写成
bestcost_serviced_at[j] =
min(0<i<j: bestcost_serviced_at[i] + C[j] s.t. D[j]-D[i] <= 100)
因为假设车辆实际停在 j 站进行维修，则递归给出了最优成本。
那么问题的解决方法是
min (j: bestcost_serviced_at[j] s.t. highway_end - D[j] <= 100)
我认为贪心算法行不通。
关于algorithm - 成本最低的类似加油站的算法？贪心还是DP？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21374496/