PKU3659-Cell Phone Network

題目：http://poj.org/problem?id=3659
有個由n個點組成的無根樹
選一個點建收訊塔，那麼該點和相鄰的點都可以收到訊號
問最少要蓋幾個塔才能覆蓋全部n個點
(即最小支配集)

程式碼：http://codepad.org/CS66AwTl
【解法一：樹形DP】

當時一開這題就想樹形DP、設計兩種狀態(有蓋和沒蓋)
確切來說是按照DFS樹的順序「DP[n][0]蓋了以後自己和子樹最優解」、「D[n][1]沒蓋自己和子樹最優」
但是發現這樣會有個不小的問題，那葉節點的狀態怎麼表示…？
(葉結點沒有子樹，沒蓋的話就bye了、無法滿足最初設計狀態的定義)

其實倒是可以設定它是無限大，但是考慮一下[0]的轉移：

DP[n][0] = (所有子節點t) min(DP[t][0],DP[t][1])
(如果蓋了n點，那麼根據定義它鄰近的結點蓋或不蓋都無所謂)

這樣的系統就無法表達完整了、因此設計加入第三個狀態成了：
DP[n][0]：在n點蓋塔，自己和子樹的最優解
DP[n][1]：n點不蓋塔，自己和子樹的最優解
DP[n][2]：n點不蓋塔，自己無所謂、子樹的最優解

用原本準備好算[1]的方法先算[2]
再來設計一個minuse，子樹在選的時候、有可能全部選"不蓋"
這時候就要選一個最小的成本、把其中一個不蓋的狀態換成蓋
(也就是說，只要有選蓋、minuse就可以是0)

算完[2]以後，發現這點是葉節點，那麼[1]理所當然就是無限大
否則[1]=[2]+minuse

【解法二：貪心】
「按照後序遍歷，發現一個點沒覆蓋、就直接蓋它的父結點」
這是從網上google得到的貪心法
其實從DP狀態發現，三個差異狀態其實差異不會太大
實際我想到一種感性的簡略證明：
(1)只有兩個節點，選哪一個都沒差

(2)是鏈狀的情形，幾乎可以兩個兩個一對、參考(1)的情形

(3)是星狀的情形(有個點分支度超過2)，我們說有個中央點好了，顯然選中央點是「很不錯的」
因為(1)選一個蓋兩個、(2)選一個蓋三個，選中央不就可以選一個蓋n個嗎
由於後序遍歷都會優先問到葉結點、才問上來
中央點的層級總是相對地高、相對地容易被選到

而假如沒選到中央點，就表示子樹剛好都是點數3的倍數的(2)或是類似的情形
沒必要選中央、選中央的父結點就更有機會蓋到更多的點

【總結】
算法導論把貪心和DP放得很近
並且重點強調「最優子結構」
能貪心選擇的問題都有最優子結構
能DP的問題都有最優子結構
而能貪心的問題幾乎也可以說是能DP(看怎麼解釋)

有時候覺得很多分治的思想、資料結構的設計思想，
和DP總有些氣味相投
我想是因為現今網路上流傳的DP一類問題
很好的體現了資訊科學的一些核心精神(各個擊破或是只做重要的事)
而且得到不少養分，發展出各種形式和優化(DAG.樹形.狀態壓縮.四邊型不等式…)
也難怪DP和相關問題會在比賽出題裡那麼熱門了

說不定可以考慮一種教算法的策略是「上課全部教DP，其他開題單回家自己學」喔
這真是先決假設「DP問題有最好的啟發性」的一種貪心策略