How would you look at developing an algorithm for this hotel problem? -

there problem working on programming course , having trouble developing algorithm suit problem. here is:

you going on long trip. start on road @ mile post 0. along way there n hotels, @ mile posts a1 < a2 < ... < an, each ai measured starting point. places allowed stop @ these hotels, can choose of hotels stop at. must stop @ final hotel (at distance an), destination. you'd ideally travel 200 miles day, may not possible (depending on spacing of hotels). if travel x miles during day, penalty day (200 - x)^2. want plan trip minimize total penalty is, sum, on travel days, of daily penalties. give efficient algorithm determines optimal sequence of hotels @ stop.

so, intuition tells me start back, checking penalty values, somehow match them going forward direction (resulting in o(n^2) runtime, optimal enough situation).

anyone see possible way make idea work out or have ideas on possible implmentations?

if x marker number, ax mileage marker, , px minimum penalty marker, can calculate pn marker n if know pm markers m before n.

to calculate pn, find minimum of pm + (200 - (an - am))^2 markers m am < an , (200 - (an - am))^2 less current best pn (last part optimization).

for starting marker 0, a0 = 0 , p0 = 0, marker 1, p1 = (200 - a1)^2. starting information can calculate p2, p3 etc. pn.

edit: switched java code, using example op's comment. note not have optimization check described in second paragraph.

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};     (int = 2; <= 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;             }         }     }     (int = 1; < hotellist.length; i++) {         system.out.print("hotel: " + hotellist[i] + ", penalty: " + penalties[i] + ", path: ");         printpath(path, i);         system.out.println();     } } 

output is:

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