algorithm - 成本最低的类似加油站的算法？贪心还是DP？

Question

我在高速公路上有一组 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 解决方案？

Answer 1

递归最好写成

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)

我认为贪心算法行不通。