算法和數據結構一直以來都是程序員的基本内功，可以說沒有數據結構的基礎建設和算法加持，也就沒有這将近八十年的信息革命時代。數據結構可以看作是算法實現的容器，通過一系列特殊結構的數據集合，能夠将算法更為高效而可靠的執行起來。

算法的應用不單隻體現在編程中。狹義的來講，算法可看作是數據傳遞和處理的順序、方法和組成方式，就像是各種排序算法等。而廣義的來講，算法更像是一種事物運行的邏輯和規則。太陽東升西落，海水潮汐潮流，月兒陰晴圓缺，這些或許都可以看似一種算法，隻不過執行者不是電的計算機，而是自然萬物。

聊遠了。所以對于算法的理解，重要的是領悟其思想，感受其内在。有同學或許就會說了，「算法不就是Leetcode，不就是刷題嘛 」。

片面了啊。題總是刷不完的，但是算法的思想就那麼幾個。所以呢，刷了那麼多題的你，還不了解這幾個常見的算法思想，想必是應該好好反省反省下了。

首先，最為簡單的思想，枚舉算法。枚舉也叫窮舉，顧名思義，就是窮盡列舉。枚舉思想的應用場景十分廣泛，也非常容易理解。簡單來說，枚舉就是将問題的可能性依次列舉出來，然後一一帶入問題檢驗，從而從一系列可能解中獲得能夠解決問題的精确解。

枚舉雖然看起來簡單，但是其實還是有一些容易被人忽視的考慮點。比方說待解決問題的「可能解/候選解」的篩選條件，「可能解」之間相互的影響，窮舉「可能解」的代價，「可能解」的窮舉方式等等。

很多時候實際上不必去追求高大上的複雜算法結構，反而大道至簡，采用枚舉法就能夠很好的規避系統複雜性帶來的冗餘，同時或許在一定程度上還能夠對空間進行縮減。

枚舉思想的流程可以用下圖來表示。通過實現事先确定好「可能解」，然後逐一在系統中進行驗證，根據驗證結果來對「可能解」進行分析和論證。這是一種很明顯的結果導向型的思想，簡單粗暴地試圖從最終結果反向分析「可能解」的可行性。

不過，枚舉思想的劣勢當然也很明顯。在實際的運行程序中，能夠直接通過枚舉方法進行求解的問題少之又少。而當「可能解」的篩選條件不清晰，導緻「可能解」的數量和範圍無法準确判斷時，枚舉就失去了意義。

然而當「可能解」的規模比較小，同時依次驗證的過程容易實施時，枚舉思想不失為一種方便快捷的方式。隻不過在具體使用時，還可以針對應用場景對「可能解」的驗證進行優化。

這種優化可以從兩個方向入手，一是問題的簡化，盡可能對需要處理的問題進行模型結構上的精簡。這種精簡具體可體現在問題中的變量數目，減少變量的數據，從而能夠從根本上降低「可能解」的組合。

二是對篩選「可能解」的範圍和條件進行嚴格判斷，盡可能的剔除大部分無效的「可能解」。

雖說如此，但是一般而言大部分枚舉不可用的場景都是由于「可能解」的數量過多，無法在有限空間或有限時間内完成所有可能性的驗證。不過實際上枚舉思想是最接近人的思維方式，在更多的時候是用來幫助我們去「理解問題」，而不是「解決問題」。

百錢買百雞問題。 該問題叙述如下：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，則翁、母、雛各幾何？

翻譯過來，意思是公雞一個五塊錢，母雞一個三塊錢，小雞三個一塊錢，現在要用一百塊錢買一百隻雞，問公雞、母雞、小雞各多少隻？

遞推思想跟枚舉思想一樣，都是接近人類思維方式的思想，甚至在實際生活具有比枚舉思想更多的應用場景。人腦在遇到未知的問題時，大多數人第一直覺都會從積累的「先驗知識」出發，試圖從「已知」推導「未知」，從而解決問題，說服自己。

事實上，這就是一種遞推的算法思想。遞推思想的核心就是從已知條件出發，逐步推算出問題的解。實現方式很像是初高中時我們的數學考卷上一連串的「因為」「所以」。那個時候還是用三個點來表示的。

而對于計算機而言，複雜的推導其實很難實現。計算機擅長的是執行高密度重複性高的工作，對于随機性高變化多端的問題反而不好計算。相比之下，人腦在對不同維度的問題進行推導時具有更高的自由度。

比方說，人腦可以很容易的從「太陽從東邊升起」推出「太陽從西邊落下」，然後大緻推出「現在的時間」。但是對于計算機而言并沒有那麼容易，你可能需要設置一系列的限制條件，才能避免計算機推出「太陽/月亮/星星」從「南/北/東邊」「落下/飛走/掉落」的可能性。

我說這個例子的用意是在說明，計算機在運用遞推思想時，大多都是重複性的推理。比方說，從「今天是1号」推出「明天是2号」。這種推理的結構十分類似，往往可以通過繼而往複的推理就可以得到最終的解。

遞推思想用圖解來表示可以參見下圖。每一次推導的結果可以作為下一次推導的的開始，這似乎跟叠代、遞歸的思想有點類似，不過遞推的範疇要更廣一些。

兔子問題。 定一對大兔子每月能生一對小兔子，且每對新生的小兔子經過一個月可以長成一對大兔子,具備繁殖能力，如果不發生死亡，且每次均生下一雌一雄，問一年後共有多少對兔子？

說完遞推，就不得不說說它的兄弟思想——遞歸算法。二者同樣都帶有一個「遞」字，可以看出二者還是具有一定的相似性的。「遞」的理解可以是逐次、逐步。在遞推中，是逐次對問題進行推導直到獲得最終解。而在遞歸中，則是逐次回歸叠代，直到跳出回歸。

遞歸算法實際上是把問題轉化成規模更小的同類的問題，先解決子問題，再通過相同的求解過程逐步解決更高層次的問題，最終獲得最終的解。所以相較于遞推而言，遞歸算法的範疇更小，要求子問題跟父問題的結構相同。而遞推思想從概念上并沒有這樣的約束。

用一句話來形容遞歸算法的實現，就是在函數或者子過程的内部，直接或間接的調用自己算法。所以在實現的過程中，最重要的是确定遞歸過程終止的條件，也就是叠代過程跳出的條件判斷。否則，程序會在自我調用中無限循環，最終導緻内存溢出而崩潰。

遞歸算法的圖解可如下圖。很明顯，遞歸思想其實就是一個套娃過程。一般官方都是嚴禁套娃行為的。所以在使用時一定要明确「套娃」舉動的停止條件，及時止損。

漢諾塔問題。 源于印度傳說中，大梵天創造世界時造了三根金鋼石柱子，其中一根柱子自底向上疊着64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次隻能移動一個圓盤。

分治，分而治之。

分治算法的核心步驟就是兩步，一是分，二是治。但這還引申出了一系列的問題，為什麼分，怎麼分，怎麼治，治後如何。

分治算法很像是一種向下管理的思想，從最高級層層劃分，将子任務劃分給不同的子模塊，進而可以進行大問題的拆分，對系統問題的粒度進行細化，尋求最底層的最基本的解。這樣的思路在很多領域都有運用，比如幾何數學中的正交坐标、單位坐标、基的概念等，都是通過将複雜問題簡化為基本的子問題，然後通過先解決子模塊再逐步解決主模塊。

在實際的運用中，分治算法主要包括兩個維度的處理，一是自頂向下，将主要問題劃分逐層級劃分為子問題；二是自底向上，将子問題的解逐層遞增融入主問題的求解中。

那為什麼要分？這個很好解釋，由于主要問題的規模過大，無法直接求解，所以需要對主要問題進行粒度劃分。

那怎麼分？遵循計算機的最擅長的重複運算，劃分出來的子問題需要相互獨立并且與原問題結構特征相同，這樣能夠保證解決子問題後，主問題也就能夠順勢而解。

怎麼治？這就涉及到最基本子問題的求解，我們約定最小的子問題是能夠輕易得到解決的，這樣的子問題劃分才具有意義，所以在治的環節就是需要對最基本子問題的簡易求解。

之後如何？子問題的求解是為了主問題而服務的。當最基本的子問題得到解後，需要層層向上遞增，逐步獲得更高層次問題的解，直到獲得原問題的最終解。

分治思想的圖解可見下圖。通過層層粒度上的劃分，将原問題劃分為最小的子問題，然後再向上依次得到更高粒度的解。從上而下，再從下而上。先分解，再求解，再合并。

歸并排序。

講完分治，我們知道分治思想最重要的一點是分解出的子問題是相互獨立且結構特征相同的。這一點并不是所有問題都能滿足，許多問題的劃分的子問題往往都是相互重疊且互相影響的，那麼就很難使用分治算法進行有效而又幹淨的子問題劃分。

于是乎，動态規劃來了。動态規劃同樣需要将問題劃分為多個子問題，但是子問題之間往往不是互相獨立的。當前子問題的解可看作是前多個階段問題的完整總結。因此這就需要在在子問題求解的過程中進行多階段的決策，同時當前階段之前的決策都能夠構成一種最優的子結構。這就是所謂的最優化原理。

最優化原理，一個最優化策略具有這樣的性質，不論過去狀态和決策如何，對前面的決策所形成的狀态而言，餘下的諸決策必須構成最優策略。同時，這樣的最優策略是針對有已作出決策的總結，對後來的決策沒有直接影響，隻能借用目前最優策略的狀态數據。這也被稱之為無後效性。

動态規劃是在目前看來非常不接近人類思維方式一種算法，主要原因是在于人腦在演算的過程中很難對每一次決策的結果進行記憶。動态規劃在實際的操作中，往往需要額外的空間對每個階段的狀态數據進行保存，以便下次決策的使用。

動态規劃的求解思路如下圖解。動歸的開始需要将問題按照一定順序劃分為各個階段，然後确定每個階段的狀态，如圖中節點的F0等。然後重點是根據決策的方法來确定狀态轉移方程。也就是需要根據當前階段的狀态确定下一階段的狀态。

在這個過程中，下一狀态的确定往往需要參考之前的狀态。因此需要在每一次狀态轉移的過程中将當前的狀态變量進行記錄，方便之後的查找。

動态規劃主要就是用來解決多階段決策的問題，但是實際問題中往往很難有統一的處理方法，必須結合問題的特點來進行算法的設計，這也是這種算法很難真正掌握的原因。

背包問題。 有 n 件物品和容量為 m 的背包，給出物品的重量以及價值。求解讓裝入背包的物品重量不超過背包容量且價值最大 。

貪心算法，我願稱之為最現實的算法思想。

人活在世上，不可能每一個選擇都那麼恰到好處。那麼多的問題，不可能所有問題都能找到最優解。很多問題根本沒有準确解，甚至于無解。所以在某些場景下，傻傻的去追求問題的最精确解是沒有意義的。

有人說，那還有最優解呢。難道最優解都不要了嗎？

沒錯，許多問題雖然找不到最精确的解，但是的确會存在一個或者一些最優解。但是一定要去追求這些最優解嗎？我看不一定。

算法的存在不是單純的為了對問題求解，更多的是提供一種「策略」。何謂「策略」，解決問題的一種方式，一個角度，一條路。所以，貪心思想是有價值的。

說回貪心算法。從貪心二字就可得知，這個算法的目的就是為了「貪圖更多」。但是這種貪心是「目光短淺」的，這就導緻貪心算法無法從長遠出發，隻看重眼前的利益。

具體點說，貪心算法在執行的過程中，每一次都會選擇最大的收益，但是總收益卻不一定最大。所以這樣傻白甜的思路帶來的好處就是選擇簡單，不需要糾結，不需要考慮未來。

貪心算法的實現過程就是從問題的一個初始解出發，每一次都作出「當前最優」的選擇，直至遇到局部極值點。貪心所帶來的局限性很明顯，就是無法保證最後的解是最優的，很容易陷入局部最優的情況。

但是它每一次做選擇的速度很快，同時判斷條件簡單，能夠比較快速的給出一種差不多的解決方案。這裡的圖解我用下圖來表示。

這個圖表示的是求解對多條直線的交點。很顯然，下圖中的直線是不存在統一交點的，但是可以通過算法求得統一交點的最優解。若是采用貪心算法，那麼在進行叠代時，每一次都會選擇離此時位置最近的直線進行更新。這樣一來，在經過多次叠代之後，交點的位置就會在某一片區域無限輪回跳轉。而這片區域也就是能求得出的大緻的最優解區域。

旅行推銷員問題。 給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路。

蒹葭蒼蒼，白露為霜。所謂伊人，在水一方。溯洄從之，道阻且長。溯遊從之，宛在水中央。

每每提及回溯，都會忍不住想到「蒹葭」裡的這句詩。看到心中所懷念的心上人啊，忍不住逆流而上去追尋她，盡管追随的道路險阻又漫長；又順流而下繼續尋覓，感覺她似乎就在河水中央。回溯算法的過程正如追逐愛情般的艱辛和反複，時而溯洄從之，時而溯遊從之。

回溯算法也可稱作試探算法，是不是讓你回憶起了在女神面前的小心翼翼。簡單來說，回溯的過程就是在做出下一步選擇之前，先對每一種可能進行試探；隻有當可能性存在時才會向前邁進，倘若所有選擇都不可能，那麼則向後退回原來的位置，重新選擇。

這樣看起來，回溯算法很像是一種進行中的枚舉算法，在行進的過程中對所有可能性進行枚舉并判斷。常用的應用場景就在對樹結構、圖結構以及棋盤落子的遍曆上。

舉一個很簡單的例子，看下面圖解。假設目的是從最O0到達O4，需要對所有節點進行回溯遍曆路徑。那麼回溯算法的過程則需要在前進的每一步對所有可能的路徑進行試探。

比方說，O0節點前進的路徑有三條，分别是上中下條的O1。回溯過程的開始，先走上面的O1，然後能夠到達上面 O2，但是這時是一條死路。那麼就需要從O2退回到O1，而此時O1的唯一選擇也走不通，所以還需要從O1退回到O0。然後繼續試探中間的O1。

回溯算法的過程就是不斷進行這樣的試探、判斷、退回并重新試探，直至找到一條完整的前進路徑。隻不過在這個過程中，可以通過「剪枝」等限制條件降低試探搜索的空間，從而避免重複無效的試探。比方說上下的O2節點，在經過O0-O1-O2的試探之後，就已經驗證了該節點不可行性，下次就無須從O1開始重複對O2的試探。

回溯思想在許多大規模的問題的求解上都能得到有效的運用。回溯能夠将複雜問題進行分步調整，從而在中間的過程中可對所有可能運用枚舉思想進行遍曆。這樣往往能夠清晰的看到問題解決的層次，從而可以幫助更好的理解問題的最終解結構。

案例

八皇後問題。 在8×8格的國際象棋上擺放8個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

模拟

模拟思想的理解相比上述思想應該不是什麼難事。

許多真實場景下，由于問題規模過大，變量過多等因素，很難将具體的問題抽象出來，也就無法針對抽象問題的特征來進行算法的設計。這個時候，模拟思想或許是最佳的解題策略。

模拟的過程就是對真實場景盡可能的模拟，然後通過計算機強大的計算能力對結果進行預測。這相較于上述的算法是一種更為宏大的思想。在進行現實場景的模拟中，可能系統部件的實現都需要上述幾個算法思想的參與。

模拟說起來是一種很玄幻的思想，沒有具體的實現思路，也沒有具體的優化策略。隻能說，具體問題具體分析。

那應該怎麼樣來圖解呢。我的理解是自定義的，任意的輸入，不規則的系統響應，但是隻為了獲得一個可靠的理想的輸出。

總結

算法思想這種東西，實際上是很玄幻的。同一種問題，或許在實現上可以采用不同的思想進行。這八種思想也不是想象中那麼高的獨立性，很多思想都是雜糅在一起的，隻是角度和側重點不同。上面這些案例也不代表單隻能用一種思想來解答，隻是用來體會一下對應的算法思想。

作為底層的程序員，雖說不需要每天刷題，但是基礎的算法思想還是需要有的。這種東西不是具體于某個算法，而是在于更高層次的對于系統或者需求的理解。

如獨立之精神，自由之思想般。

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部