電腦正在升級系統(tǒng)，我上來稍稍溜達(dá)溜達(dá)。
今天找磊哥給我講了講動態(tài)規(guī)劃，真心受益，為了防止以后忘了，總結(jié)一下先。
磊哥是從尋找一個(gè)有向無環(huán)圖的最短路講起的，有向無環(huán)圖的講法參看《算法導(dǎo)論》，在這里我就不重復(fù)說一遍了，因?yàn)槲覍?shí)在是沒有辦法把圖畫出來。
實(shí)際上磊哥解決了我的一個(gè)疑惑，利用他的經(jīng)驗(yàn)。
做 動態(tài)規(guī)劃題對我來說最為鬧心的就是尋找狀態(tài)，尋找最優(yōu)子結(jié)構(gòu)，貌似這兩個(gè)一有困難動態(tài)規(guī)劃的題根本就沒法做了。磊哥告訴我的做法就是枚舉狀態(tài)，所謂枚舉狀 態(tài)就是把這道題所有可能當(dāng)狀態(tài)的東西都列出來，然后一個(gè)個(gè)去進(jìn)行排除。排除的過程是這樣的，首先要進(jìn)行定義，也就是說要明確這個(gè)狀態(tài)到底是什么，有什么用 處，然后再用這個(gè)狀態(tài)畫有向無環(huán)圖，如果畫有向無環(huán)圖的過程中推理出由這個(gè)狀態(tài)，后面的根本無法實(shí)現(xiàn)或者說出現(xiàn)了矛盾，那么這個(gè)狀態(tài)就是錯(cuò)的，最終一定能 夠枚舉出來一個(gè)正確的狀態(tài)。
/*一說到枚舉，就要考慮一下時(shí)間復(fù)雜度，但是我認(rèn)為這個(gè)可以忽略不計(jì)，就算是對于人腦來說，因?yàn)橐坏李}之中貌似能找出來的狀態(tài)應(yīng)該不能超過手指能查找的范圍。好吧，以上是僅供娛樂的題外話。*/
枚 舉出來一個(gè)正確的狀態(tài)之后，那么就要進(jìn)入下一個(gè)糾結(jié)的狀態(tài)，那就是尋找最優(yōu)子結(jié)構(gòu)，磊哥的做法我認(rèn)為非常高明，那就是我前文所提到的有向無環(huán)圖，以狀態(tài)當(dāng) 結(jié)點(diǎn)，轉(zhuǎn)化關(guān)系當(dāng)作邊權(quán)，畫有向無環(huán)圖，然后參照著有向無環(huán)圖的那種方式來尋找最優(yōu)子結(jié)構(gòu)，但是糾結(jié)的就是怎么做邊權(quán)，這個(gè)確實(shí)鬧心，這塊硬骨頭只能是一 點(diǎn)點(diǎn)去啃了。
最優(yōu)子結(jié)構(gòu)推出來以后，下一步就是推狀態(tài)轉(zhuǎn)移方程，這個(gè)沒有別的辦法，就是用最優(yōu)子結(jié)構(gòu)中所體現(xiàn)的轉(zhuǎn)化關(guān)系來推狀態(tài)轉(zhuǎn)移方程了……
以上這些是磊哥給我講的東西的總結(jié)版，目測回憶起來應(yīng)該是全的，然后按照磊哥的指令（也是執(zhí)行飛哥說的這個(gè)月開始推動態(tài)規(guī)劃的計(jì)劃），應(yīng)該繼續(xù)尋求動態(tài)規(guī)劃入門，磊哥的意思是做一堆水題練練思想，那么就做吧……然后就應(yīng)該百度一下DP水題，開始刷，刷一段時(shí)間水題吧，怎么說呢，練練思想，先入了動態(tài)規(guī)劃的門，高級動態(tài)規(guī)劃有我啃的呢！
飛哥給我定的計(jì)劃應(yīng)該是嚴(yán)格執(zhí)行的，然后我自己定的那個(gè)比較山寨的學(xué)習(xí)計(jì)劃也應(yīng)該執(zhí)行下去，畢竟數(shù)據(jù)結(jié)構(gòu)也是個(gè)傷，本學(xué)期好歹要把數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)拿下了，動態(tài)規(guī)劃入門了……