95全國賽 快遞服務

題目：

快遞公司有三名司機，現在有 n ( <= 200 )個地點，已知任兩點之間的來往的最少

耗油量，給定一串長度為 m ( <= 1000 )的送件地點順序，司機最初分別在地點

1, 2, 3，請輸出送完所有貨物的最少總耗油量。

解法：

首先可以觀察到，下一個送貨地點只和當前司機所在的位置有關，和司機之前走過

的點無關，無後效性使我們可以很容易想到 DP 的做法，最初可以想到用三個司機的

位置當作狀態，但事實上某一個維度是沒有意義的，當前的三個位置中必然有

當前的送貨點，於是可以將狀態壓為二維後解決，之所以記錄這題的原因是想討論

一下轉移的部分，若使用 top-down 的方式，沒有考慮周全的話很容易寫成 

dp'[n][m] = 

min{ dp[n][m] + oil[last][now], dp[n][now] + oil[last][m], dp[now][m] + oil[last][n] } 

事實上對於 dp'[i][j]，若是 last == i || last == j ，則會有許多狀態未被轉移到，必須要

加上一些條件造成編程的麻煩，但若是使用 bottom-up 的方式，轉移則是將三個地點

分別推到下一個目標點即可，非常簡短方便。

從此題可以清楚看出，選擇對的 DP 順序在實作上確實有很大的益處。