算導之DP算法的設計心得

和其他的DP文章隻是灌輸思考之後的結果不同，這篇是DP算法的自我體會，應該是設計DP算法的思考過程。

斯以為，這才是拿到一問題，從思考到解決最精華的部分：）

猶記得第一次看到算法導論上拿最長與最短路徑來說明DP中最優子結構證明過程的一個細節的時候，心裡激動不已，國内的教材完全不考慮這個，而是把偉人思考之後的東西呈現給新人。

我第一看到，心想，這就是我要的東西，包括之前的loop invariant也是如此，看國内教材時缺失而又如此渴望的東西，在算導中再次給出完美的答案。

尋找最優子結構：

1. 可以是做一個選擇，例如從前兩個裝配線的加工點中選一個，汽車裝配問題；從K-1個位置中選一個斷開Matrix Chain；

2. 做出這樣一個選擇後，問題分為了哪一個或幾個子問題，進行描述。

3. 利用“剪切”技術來證明具有最優子結構性質（其實貪心也是這麼做的）

矩陣鍊裂解為兩個矩陣鍊，最後選出的斷鍊位置一定導緻對應兩個矩陣鍊的最小乘法次數(最優解)，如果有更優的話，就用更優的去替換目前的，将導緻新的目前的解最優，而與目前矩陣鍊的解是最優的産生沖突。

汽車裝配同理

*注意：這裡有一個比較重要的點要提，做出選擇分成多個子問題後，子問題之間必須互不影響(或者有影響，經過處理後，可以變得沒有影響，且不破壞最優性質)，否則不能證明最有子結構性質。具體地(算導翻譯Specifically為特别地，應該不夠準确)，如果替換了其中一個的更優的解，然而卻使其他子問題變差了，就不能嚴格證明最後導緻

新的目前的解更優，進而不能産生沖突，也就不從證明。典型反例就是試圖證明最長簡單路徑問題的最優子結構性質。

4. 最重要的一點，就是設計子問題空間了，怎麼用數學語言表達？

設計這種東西都是有點隻可意會不可言傳的。算導是這樣說的，先盡量保持空間簡單(哲學KISS原則，刮胡刀原理)，然後再需要時擴充。後面這個例子特别貼切。

如果對汽車裝配問題模組化，需要S1[j] S2[j]即可，因為每次的選擇都是産生一個子問題，也即S1[j-1] S2[j-1],而矩陣鍊乘法由于選擇裂解成兩個子問題，如果用A[j]表示A1...Aj的最優解，如果在Ak斷開，前面A1...Ak表示為A[k]，而後面的

Ak+1..Aj不能用這種子問題空間表示，是以需要将子問題空間修改為A[i,j]這樣一個二維數組。

針對子問題之間獨立，互不影響，據下面的例子。

考慮下面兩個問題，無權最短(簡單)路徑和無權最長(簡單)路徑，

注：此處->未必是一條邊

試圖證明最長路徑，x->y->z為到z的最長路徑的一個選擇, 欲證明x->y，y->z也是相應子問題的最長路徑。但是若x->y出現了結點u,y->z也出現了u,那麼雖然兩個子問題都是最長簡單路徑，但是拼接起來不是簡單路徑了。是以用剪切技術不能證明。

假如這個x到z的最長路徑，x->y，y->z是對應問題的最長路徑麼？不是！如果試圖剪接的話，發現兩個更優的解拼接起來不是簡單路徑了，是以不能拼接。

試圖證明試圖證明最短路徑，x->y->z為到z的最短路徑的一個選擇, 欲證明x->y，y->z也是相應子問題的最短路徑。若x->y出現了結點u,y->z也出現了u, 可以将前段的u->y和y->u去掉，得到的結果一定更優。不可能出現比x->y y->z的更優解了，如果出現了，

可以用更優的替換，進而得出更優的解，如果重複結點，按照上述删除兩段路徑。

為啥上面沒這麼做呢，因為删除掉兩端之後，隻能保證比之前的短，不能保證比之前長(不可能)，這也是兩者最微妙之處。

這裡面涉及到了一個細節：做出選擇後，一個子問題劃分成的多個子問題要獨立(沒有重複頂點)，或者不獨立，經過操作(删除兩端重複的路徑)可以獲得正确的更優的解(更短的路徑)。

最後順便套上偶像的話，這篇文章是我想看背包問題，然後複習DP時臨時想寫的，對以後設計DP都會有幫助，周董說過，想到一件事情、idea，就要立馬去做，不能等，否則以後可能就不會去做了：）