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