算法，包含的問題很多。解決一個(gè)算法的過程，是一個(gè)工程的過程。不僅需要從數(shù)學(xué)角度，獲得抽象，獲得問題可解性，以及復(fù)雜度的相關(guān)估計(jì)，還需要用語言，庫(kù)，系統(tǒng)調(diào)用將其實(shí)現(xiàn)，這就需要一些積累的經(jīng)驗(yàn)。兩者共同決定著一個(gè)算法問題的解決是否有效，是否優(yōu)雅，是否可維護(hù)，是否易擴(kuò)展。下面就從兩個(gè)方面說說算法問題的解決。也為自己整理一下思路。
第0是仔細(xì)看題，常常幾個(gè)字的差別，題目的意思是完全不一樣的，要知道，NP問題其實(shí)和多項(xiàng)式問題，就差了幾個(gè)字哦。這點(diǎn)我深有體會(huì)，經(jīng)常看了結(jié)題報(bào)告才發(fā)現(xiàn)原來題目沒有想象中的那么難。囧。審題可以從以下幾個(gè)方面入手：1 數(shù)據(jù)范圍 2 給的case 手動(dòng)理解答案
第一是數(shù)學(xué)角度。數(shù)學(xué)抽象是所有問題的第一步，從一個(gè)實(shí)際的模型，獲得一個(gè)解的模型，其實(shí)屬于數(shù)學(xué)建模的范疇。好在一般算法題都是從抽象問題轉(zhuǎn)化而來，給出的條件常常很特殊，相信有一定做題量以后就能很快的進(jìn)行建模。建模，首先必須有個(gè)初步的模型，才能在腦海中建立起適合問題的模型。這就需要算法經(jīng)驗(yàn)。在這方面，將基礎(chǔ)題一種一種過一遍是很好的方法。這使得你的腦海中起碼知道一些基本的模型。舉例來說，求最優(yōu)解問題時(shí)候，就會(huì)自覺的想到最優(yōu)解的幾種模型，是貪心的，還是動(dòng)態(tài)規(guī)劃的，或是NP難的，在看到配對(duì)，關(guān)系的問題時(shí)，想到是否可以用有向圖，無向圖，樹形圖來表示關(guān)系，然后用并查集，最短路，最大流等經(jīng)典算法。當(dāng)求問題可能解時(shí)，是否用回溯模型，或者用遞歸。抽象是開始一個(gè)問題時(shí)，是我最頭疼的一步，因?yàn)楸旧頉]有定法。我做題往往將問題抽象不夠，最后得到的算法又臭又長(zhǎng)。這也是我喜歡模擬題的原因，單從建模方面，很簡(jiǎn)單，只要足夠細(xì)心，一定能得到結(jié)果。 判斷一個(gè)抽象優(yōu)劣的標(biāo)準(zhǔn)就是問題能否變得簡(jiǎn)單。這里的簡(jiǎn)單分為兩個(gè)方面：能并入現(xiàn)有問題的，能將問題簡(jiǎn)單化的。第一點(diǎn)，算法常常是某個(gè)或某幾個(gè)問題的特例，套用前人的算法，證明都省了，而后者就需要自己分析問題了。這和解一道數(shù)學(xué)題的過程是一樣的，從已知推到未知，從復(fù)雜化簡(jiǎn)。思路當(dāng)然有幾個(gè)方面，常用的有：1 改變條件：去掉限制條件，或者加上特例條件，這樣常?？梢垣@得解的直觀印象， 也可以區(qū)分一些貪心和dp問題。2 分治 這是通用的思路，一個(gè)問題可以分為幾個(gè)子問題，子問題是否也是主問題的一種，子問題的最優(yōu)解是否是主問題最優(yōu)解。 完成以后，就可以開始考慮復(fù)雜度了。通常是先給出一種可解方案，再改進(jìn)復(fù)雜度。
第二就是工程問題了。這直接決定你的代碼是否清晰，可讀，易懂?，F(xiàn)在算法往往采用全局變量的聲明方法避免過多的參數(shù)傳遞，變量也簡(jiǎn)短概括，頗有數(shù)學(xué)表達(dá)式的氣勢(shì)。況且有程序設(shè)計(jì)實(shí)踐中提到的，在局部作用域名字應(yīng)該簡(jiǎn)短的條款，那就大膽的采用最簡(jiǎn)單的變量吧。工程中最重要的其實(shí)是數(shù)據(jù)結(jié)構(gòu)。開始做bfs經(jīng)常用到隊(duì)列，而數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列實(shí)現(xiàn)不然用鏈表，不然就搞的復(fù)雜無比，這導(dǎo)致了很多需要用隊(duì)列的題目我拿到以后很是害怕。最后，發(fā)現(xiàn)在算法中，基本沒人用new delete這樣的操作符，取而代之的是超大數(shù)組來實(shí)現(xiàn)鏈表。大家的理念是，用完就用下一個(gè)。這確實(shí)讓很多問題簡(jiǎn)單化了。但是，隨著問題越來越復(fù)雜，需要的數(shù)據(jù)結(jié)構(gòu)往往也隨著復(fù)雜了?？纯此惴▽?dǎo)論里面那幾章，從二叉索引樹，到紅黑樹，到B樹，二項(xiàng)堆，斐波那契堆，這幾章到現(xiàn)在我還沒理解。這些數(shù)據(jù)結(jié)構(gòu)都優(yōu)化了數(shù)據(jù)操作，但是實(shí)現(xiàn)復(fù)雜，這時(shí)候就需要庫(kù)出現(xiàn)了。algorithm頭文件的出現(xiàn)，讓coder少寫了不少經(jīng)典算法，stl也將數(shù)據(jù)結(jié)構(gòu)的春風(fēng)吹到了算法圈。而boost庫(kù)，則是在實(shí)用工程中可以看做stl一樣重要的庫(kù)。有了庫(kù)的幫助，就算你不怎么會(huì)數(shù)據(jù)結(jié)構(gòu)，也能寫出很高效的程序來。
不管怎么說，實(shí)踐還是需要實(shí)踐。最簡(jiǎn)單的方法，就是你的紙和筆。沒有IDE智能提醒，你能寫出多離譜的程序來。一個(gè)好的程序員，必須聰明，寫高效，整齊的代碼。這幾個(gè)字，需要你用時(shí)間去磨練。
Good Luck!