第一個(gè)問(wèn)題我覺(jué)得我無(wú)法給出完美的答案，這里搞競(jìng)賽的牛人蠻多，不妨說(shuō)說(shuō)體會(huì):D

         我個(gè)人覺(jué)得算法里面極大一部分內(nèi)容是如何有效地進(jìn)行搜索，這里的"有效"可以分為：避免不必要的計(jì)算（如A*尋路以及所有的啟發(fā)式剪枝），緩存重復(fù)計(jì)算（如所有­的動(dòng)態(tài)規(guī)劃）。當(dāng)然，知道這些跟具體的設(shè)計(jì)出一個(gè)算法至少還有十萬(wàn)八千里，只能說(shuō)有了這個(gè)大體的思路，就可以從這兩個(gè)角度去審視手頭的問(wèn)題，往往是會(huì)有啟發(fā)意義­的罷了。如何避免不必要的計(jì)算？也有很多 rules of thumb 可以遵循，如啟發(fā)式剪枝里面就要求去設(shè)計(jì)一個(gè)最優(yōu)下界，而最一般的思路則是使勁瞅瞅問(wèn)題里面有什么條件是沒(méi)有利用的，這些條件組合起來(lái)可以得出什么性質(zhì)，也許某­個(gè)性質(zhì)就能夠被利用來(lái)減掉一大堆計(jì)算，至于如何從題目條件推出有價(jià)值的性質(zhì)，有兩個(gè)辦法，一是試錯(cuò)（想到的結(jié)論都給寫(xiě)出來(lái)，陶哲軒在 Solving Mathematical Problems 里面就提到過(guò)這個(gè)辦法。）；另一個(gè)方向則是腦袋里揣著想要實(shí)現(xiàn)的目的往反方向歸約。如何緩存重復(fù)計(jì)算？簡(jiǎn)單的動(dòng)態(tài)規(guī)劃問(wèn)題如fibonacci數(shù)列計(jì)算，其重復(fù)­計(jì)算是非常明顯的，計(jì)算的過(guò)程本身就指明了哪些計(jì)算是重復(fù)的（An 項(xiàng)的計(jì)算是重復(fù)的）——當(dāng)然，正如早前鄧同學(xué)發(fā)的一個(gè)題目<https://groups.google.com/group/pongba/browse_frm/thread/2ca1f2bda0c8...>里面說(shuō)的，其實(shí)fibonacci數(shù)列計(jì)算里面的線性變換本身也是有重復(fù)計(jì)算的——后者便是更隱蔽的重復(fù)計(jì)算了，一個(gè) non-trivial 的動(dòng)態(tài)規(guī)劃問(wèn)題往往涉及到非常隱蔽的重復(fù)計(jì)算，或者更難的是，你遍歷組合空間的方式?jīng)Q定了你所能夠緩存的重復(fù)計(jì)算到底有多少，也許某個(gè)遍歷方式之下就沒(méi)有辦法去­緩存計(jì)算。當(dāng)然，算法的范疇其實(shí)是很大的，算法是一個(gè)AI-Complete 的問(wèn)題，所有的 Problem-Solving 過(guò)程都可以叫做算法。只是有很多實(shí)際當(dāng)中的算法會(huì)掉入以上兩類(lèi)而已。 

    第二個(gè)問(wèn)題我舉一個(gè)例子：不像很多牛人在高中和本科就競(jìng)賽獎(jiǎng)牌一堆，我直到大四的時(shí)候還不知道什么是動(dòng)態(tài)規(guī)劃，因?yàn)楸究扑哪晡乙恢敝粚?duì)底層技術(shù)感興趣，最喜歡看 比如 Petzold 的《編碼的奧秘》和 Richter 的《.NET 框架程序設(shè)計(jì)》（事實(shí)上這是我看的第一本英文原版書(shū)）這類(lèi)書(shū)。研一的時(shí)候由于方向是自然語(yǔ)言處理，看的第一篇 paper 是 Rabiner 的  A Tutorial on Hidden Markov Models and Selected Applications in Speech
Recognition 。Paper 的內(nèi)容倒是完全能夠理解，但是理解其實(shí)只是第一步，我發(fā)現(xiàn)理解了之后很快就忘掉了，這就說(shuō)明理解得不夠深刻。比如里面的 Viterbi 算法，花了時(shí)間去理解，但是一轉(zhuǎn)頭很快又忘掉了。一年后因?yàn)闄C(jī)緣巧合，對(duì)算法發(fā)生了一段短暫的興趣，并學(xué)習(xí)了一些基礎(chǔ)的算法，尤其是算法的思想，因?yàn)樗枷胧怯懈F­的，但算法是無(wú)窮的，尤其是題目是做不完的。之后一段時(shí)間，碰巧又需要翻一翻馬可夫模型，搜出吳軍的數(shù)學(xué)之美以及那篇 Paper ，發(fā)現(xiàn) Viterbi 算法其實(shí)就是最簡(jiǎn)單的一類(lèi)動(dòng)態(tài)規(guī)劃，由于對(duì)于動(dòng)態(tài)規(guī)劃的理解深刻了很多，所以對(duì)于 Viterbi 算法，在腦袋里面記住的不再是什么 Forward Variable/Backward Variable
之類(lèi)的技術(shù)細(xì)節(jié)，而是它的本質(zhì)，于是便不再容易忘掉，而即便忘掉，就如龐加萊所說(shuō)，也可以非常迅速的將算法的細(xì)節(jié)自行構(gòu)建出來(lái)。

       其實(shí)我相信這樣的例子是數(shù)不勝數(shù)的，所以我這個(gè)只是算一個(gè) Yet Another Example ，由于對(duì)我來(lái)說(shuō)比較特殊，所以印象較為深刻。

        這個(gè)例子是關(guān)于"理解"的。有時(shí)候算法也會(huì)非常有用，如有一次寫(xiě)程序時(shí)需要用到 LCS 和 Edit-Distance （這樣的機(jī)會(huì)很少，但遇到了時(shí)如果不知道有多項(xiàng)式復(fù)雜度的算法就很悲慘了），而做機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的更是少不了一坨坨的算法，如果光是理解別人的做法然后實(shí)現(xiàn)­出來(lái)，那么對(duì)算法的思想的把握有助于理解和記憶；如果需要自己設(shè)計(jì)算法，那就需要算法基礎(chǔ)知識(shí)的輔助才行了。絕大多數(shù)人應(yīng)該屬于前者。

         學(xué)習(xí)到什么程度？我覺(jué)得視人群而定。如果做底層開(kāi)發(fā)、應(yīng)用開(kāi)發(fā)、系統(tǒng)開(kāi)發(fā)，只要知道一個(gè)大概就可以了，知道經(jīng)典的數(shù)據(jù)結(jié)構(gòu)和算法沒(méi)有任何困難，而且反正經(jīng)典算法­都有現(xiàn)成的庫(kù)可用。對(duì)于有興趣做一點(diǎn) research 沾邊的事情的人，則需要了解這些算法背后的一般性思路是什么，否則來(lái)一個(gè)特定的算法你就特定的理解記憶一下，肯定不牢靠，而且浪費(fèi)大腦資源。對(duì)于搞 real deal 的 original research 的那就需要廣泛的知識(shí)積累了，光知道一般性思路都不夠。

        另一方面，我覺(jué)得學(xué)完了經(jīng)典算法，深刻理解了算法背后的一般性思路之后，如果再進(jìn)一步去玩題目，做題庫(kù)。效益卻不是很大的，因?yàn)榈赌チ耸且玫模骖}目做題庫(kù)就­是進(jìn)一步磨刀而不用（不去解決實(shí)際問(wèn)題，能夠產(chǎn)生影響力的，或生產(chǎn)力的問(wèn)題）。實(shí)際上做了一些題目之后就完全沒(méi)必要進(jìn)一步做題目了，因?yàn)樽鰜?lái)做去，拼的基本也就­是誰(shuí)的知識(shí)積累多（套路多），誰(shuí)的耐心大（肯使勁去磨一道題目）；實(shí)際上誰(shuí)也不比誰(shuí)笨，到最后區(qū)別就基本上顯露在知識(shí)積累和耐心上了。所以接著做，刀也不會(huì)磨得­更鋒利，更何況大好的時(shí)光應(yīng)該去做點(diǎn)有意義的事情（如果是為了 fun 而做題的，那么有意義的事情同樣也可以是 extremely fun），比如我覺(jué)得最吸引人也最根本的問(wèn)題就是人工智能問(wèn)題（想想看，人腦是世界上迄今為止所知最為復(fù)雜的結(jié)構(gòu)，這個(gè)結(jié)構(gòu)具備了認(rèn)識(shí)自然界"規(guī)律"的能力，具­備了認(rèn)識(shí)"自我"的能力，具備了歸納和演繹推理的能力，類(lèi)比的能力，具備了難以置信的啟發(fā)式搜索能力，具備完美的模式識(shí)別能力，而根據(jù)進(jìn)化論的觀點(diǎn)，這樣的結(jié)構(gòu)­居然僅僅是通過(guò)變異——篩選得來(lái)的，如果真有上帝，那么利用上帝賦予我們的大腦去破解上帝這個(gè)頂級(jí)牛逼程序員寫(xiě)的程序——人腦的秘密，還有比這更帶勁兒的事情嗎­？），所以我覺(jué)得有那么好的基礎(chǔ)的牛人，不去直面真正 fundamental 的 problems ，就可惜了，須知題目是永遠(yuǎn)做不完的，一個(gè)公理系統(tǒng)的定理也是永遠(yuǎn)推導(dǎo)不完的，永遠(yuǎn)可以設(shè)計(jì)出題目來(lái)給你做，但是真正的問(wèn)題其實(shí)只有一個(gè)。如果窮舉不了世界上所­有的問(wèn)題，至少可以舉出那些有趣、有意義的問(wèn)題:)

--
劉未鵬(pongba)
Blog|C++的羅浮宮
http://blog.csdn.net/pongba