6.2

Road-Trip Hotel Stops

Pattern · prefix (LIS-shaped, scan back) 1-D table O(n²) 5difficulty
Question — exam style

You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a[1] < a[2] < … < a[n], where each a[i] is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance a[n]), which is your destination.

You'd ideally like to travel 200 miles a day, but this may not be possible. If you travel x miles during a day, the penalty for that day is (200 − x)². You want to plan your trip so as to minimize the total penalty — the sum, over all travel days, of the daily penalties. Design a dynamic-programming algorithm that determines the optimal sequence of hotels at which to stop.

Input:Mile posts a[1] < … < a[n] (with a[0] = 0 the start).
Output:Minimum total penalty of a valid trip ending at hotel n.

Model answer

4-part format
aSubproblem in words
T(i) = the minimum total penalty of a valid trip that starts at mile post 0 and ends at hotel i, for 0 ≤ i ≤ n.

Define a[0] = 0 and let penalty(j, i) = (200 − (a[i] − a[j]))² be the cost of driving straight from hotel j to hotel i.

bRecurrence math only, with base case + bounds
T(0) = 0 T(i) = min{ T(j) + (200 − (a[i] − a[j]))² : 0 ≤ j ≤ i-1 } for 1 ≤ i ≤ n

The last leg arrives at i from some earlier hotel j; try every j and add that leg's penalty to the best trip ending at j. Same "scan all earlier indices" shape as LIS.

cImplementation analysis
(1) # of subproblems
O(n)
(2) Time to fill table
O(n²) — O(n) per entry
(3) Where answer is extracted
T(n)
(4) Time to extract
O(1)
Format trap here

The answer is T(n) — not max/min over the table — because you are required to end at hotel n. Read the problem's fixed-endpoint condition before deciding your extraction step.

Optional pseudocode not required by Ed #9

A mechanical translation of the recurrence. The exam grades the recurrence, not this.

function Hotels(a[1..n]):   # a[0] = 0 (start)
    T[0] = 0
    for i = 1 to n:
        T[i] = ∞
        for j = 0 to i-1:
            T[i] = min(T[i], T[j] + (200 - (a[i]-a[j]))^2)
    return T[n]
✎

Try it yourself

worked example + self-test

Recurrence: T(0)=0; T(i)=min{T(j)+(200−(a[i]−a[j]))²}. Answer T(n).

Worked the optimum SKIPS a hotel

Start mile 0. Hotels a = [180, 340, 360, 540, 700] (indices 1..5). Leg penalty = (200 − distance)².

T(0) = 0 T(1) hotel 180: j=0 → (200−180)²=400 → 400 (via 0) T(2) hotel 340: j=0 → 19600 ; j=1 → 400+(200−160)²=2000 → 2000 (via 1) T(3) hotel 360: j=0 → 25600 ; j=1 → 400+(200−180)²=800 ; j=2 → 2000+(200−20)²=34400 → 800 (via 1) ← SKIP 340 T(4) hotel 540: j=2 → 2000 ; j=3 → 800+(200−180)²=1200 ; … → 1200 (via 3) T(5) hotel 700: j=3 → 20400 ; j=4 → 1200+(200−160)²=2800 ; … → 2800 (via 4)
Answer: T(5) = 2800. Optimal stops: 180, 360, 540, 700 — hotel 340 is skipped. At hotel 360 the DP rejects arriving from 340 (a tiny 20-mile leg → penalty 32400) in favor of driving 180→360. For contrast, stopping at every hotel costs 36400 — 13× worse.
Self-test work the table, then reveal

Start mile 0. Hotels a = [250, 300, 550, 780]. Same (200 − distance)² penalty; must end at 780.

Reveal answer
Minimum total penalty = 13400  (optimal stops: 250, 550, 780 — hotel 300 is skipped; stopping at all four would cost 28400).