因為 ｎ 的值不大，所以用一般的 DP （動態規劃）的想法來做即可。

首先，我們把走到每個里程點的成本設為極大的值，以便後續處理。而現在我們以

4

190 260 385 540

這組數據為例：

先看第一個里程點：

190 260 385 540

因為是第一個，前面沒有任何里程點。因此走到這裡的成本為（200 － 190）^ 2 ＝ 100。

再看第二個里程點：

190 260 385 540

可以看出，如果從第一個里程點到這裡，總成本為 100 ＋ （200 － （260 － 190））^ 2 ＝ 17000，比從起點直接過來的成本（3600）還高。所以走到這邊的最佳路徑為：0 2

再來是第三個里程點：

190 260 385 540

從起點過來的成本是 34225 ，從第二個里程點過來為 9225 ，都大過從第一點過來。

因此，到這點的最佳路徑為：0 1 3 ，成本為 125 。

最後是第四個里程點：

190 260 385 540

同上，最佳的走法是：0 1 3 4，總成本為 2150 。

因此，走到最後一個里程點的走法 0 1 3 4 ，即是所求。其他測試資料也是同理：到某一里程點，跟前面的最佳走法做結合。取成本最小的，即是從起點到此點的作家走法。以此算法算到最後一個點中途的經過的路徑即為題目要求之答案。