algorithm - 您如何看待针对该酒店问题的算法开发？

有一个问题，我正在为一个编程课程，我有困难开发一个算法，以适应这个问题。这里是：
你要去长途旅行。你从0英里处开始上路。一路上有N个
酒店，位于Mile Posts A1只有在这些旅馆你才可以停下来，但你可以选择哪家旅馆
你停在。您必须在最后一家酒店（距离A）停车，这是您的目的地。
理想情况下，您希望每天行驶200英里，但这可能是不可能的（取决于间距
在酒店里）。如果你在一天内行驶x英里，那一天的罚款是（200-x）^2。你想要的
计划您的旅行，以尽量减少总罚款，也就是说，在所有旅行日内，
每日惩罚。
给出一个有效的算法，确定酒店的最佳停车顺序。
所以，我的直觉告诉我从后面开始，检查惩罚值，然后以某种方式将它们向后匹配到前面的方向（结果是O（N^2）运行时，这对这种情况来说是最理想的）。
有没有人看到任何可能的方法来实现这个想法，或者对可能的实现有什么想法？

最佳答案

如果x是一个标记号，ax是到该标记的里程数，并且px是到达该标记的最小惩罚，那么如果您在pn之前知道所有标记n的pm，则可以计算到标记m的n。
要计算pn，请找到所有标记pm + (200 - (an - am))^2的m最小值，其中am < an和(200 - (an - am))^2小于您当前的最佳值（最后一部分是优化）。
对于起始标记pn，0和a0 = 0，对于标记p0 = 0，1。有了这些起始信息，您可以计算p1 = (200 - a1)^2，然后p2等直到p3。
编辑：使用op注释中的示例切换到java代码。注意，这没有第二段中描述的优化检查。

public static void printPath(int path[], int i) {
    if (i == 0) return;
    printPath(path, path[i]);
    System.out.print(i + " ");
}

public static void main(String args[]) {
    int hotelList[] = {0, 200, 400, 600, 601};
    int penalties[] = {0, (int)Math.pow(200 - hotelList[1], 2), -1, -1, -1};
    int path[] = {0, 0, -1, -1, -1};
    for (int i = 2; i <= hotelList.length - 1; i++) {
        for(int j = 0; j < i; j++){
            int tempPen = (int)(penalties[j] + Math.pow(200 - (hotelList[i] - hotelList[j]), 2));
            if(penalties[i] == -1 || tempPen < penalties[i]){
                penalties[i] = tempPen;
                path[i] = j;
            }
        }
    }
    for (int i = 1; i < hotelList.length; i++) {
        System.out.print("Hotel: " + hotelList[i] + ", penalty: " + penalties[i] + ", path: ");
        printPath(path, i);
        System.out.println();
    }
}

输出为：

Hotel: 200, penalty: 0, path: 1
Hotel: 400, penalty: 0, path: 1 2
Hotel: 600, penalty: 0, path: 1 2 3
Hotel: 601, penalty: 1, path: 1 2 4

关于algorithm - 您如何看待针对该酒店问题的算法开发？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4950956/