加油站式算法,成本最低？贪心还是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)

我认为贪心算法行不通。