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