最近忽然想起自己很久沒有刷過算法題了，在 Leetcode 上撿了幾題刷了一下，發現手確實生了，看到了 labuladong 大佬對數據結構和算法的理解比較深入，故做此記錄。

如果要讓我?句話總結，我想說算法的本質就是「窮舉」。

這么說肯定有人要反駁了，真的所有算法問題的本質都是窮舉嗎？沒有例外嗎？

例外肯定是有的，比如前幾天我還發了 一行代碼就能解決的算法題，這些題目類似腦筋急轉彎，都是通過觀察，發現規律，然后找到最優解法，不過這類算法問題較少，不必特別糾結。再比如，密碼學算法、機器學習算法，它們的本質確實不是窮舉，而是數學原理的編程實現，所以這類算法的本質是數學，不在我們所探討的「數據結構和算法」的范疇之內。

順便強調下，「算法工程師」做的這個「算法」，和「數據結構與算法」中的這個「算法」完全是兩碼事， 免得?些初學同學誤解。

對前者來說，重點在數學建模和調參經驗，計算機真就只是拿來做計算的工具而已；而后者的重點是計算機思維，需要你能夠站在計算機的視角，抽象、化簡實際問題，然后用合理的數據結構去解決問題。

所以，你千萬別以為學好了數據結構和算法就能去做算法工程師了，也不要以為只要不做算法工程師就不需要學習數據結構和算法。坦白說，大部分開發崗位工作中都是基于現成的開發框架做事，不怎么會碰到底層數據結構和算法相關的問題，但另?個事實是，只要你想找技術相關的崗位，數據結構和算法的考察是繞不開的，因為這塊知識點是公認的程序員基本功。

為了區分，不妨稱算法工程師研究的算法為「數學算法」，稱刷題面試的算法為「計算機算法」，我寫的內容主要聚焦的是「計算機算法」。

這樣解釋應該很清楚了吧，我猜大部分人的目標是通過算法筆試，找?份開發崗位的工作，所以你真的不需要有多少數學基礎，只要學會?計算機思維解決問題就夠了。

其實計算機思維也沒什么高端的，你想想計算機的特點是啥？不就是快嘛，你的腦回路?秒只能轉?圈，人家 CPU 轉幾萬圈無壓力。所以計算機解決問題的方式大道至簡，就是窮舉。

我記得自己剛入門的時候，也覺得計算機算法是?個很高大上的東西，每見到?道題，就想著能不能推導出 ?個什么數學公式，啪的?下就能把答案算出來。

比如你和一個沒學過計算機算法的人說你寫了個計算排列組合的算法，他大概以為你發明了一個公式，可以直接算出所有排列組合。但實際上呢？沒什么高大上的公式，后文 回溯算法秒殺排列組合子集問題 寫了，其實就是把排列組合問題抽象成一棵多叉樹結構，然后用回溯算法去暴力窮舉。

對計算機算法的誤解也許是以前學數學留下的「后遺癥」，數學題?般都是你仔細觀察，找幾何關系，列方程，然后算出答案。如果說你需要進行大規模窮舉來尋找答案，那大概率是你的解題思路出問題了。

而計算機解決問題的思維恰恰相反：有沒有什么數學公式就交給你們人類去推導吧，如果能找到?些巧妙的 定理那最好，但如果找不到，那就窮舉唄，反正只要復雜度允許，沒有什么答案是窮舉不出來的，理論上講 只要不斷隨機打亂?個數組，總有?天能得到有序的結果呢！當然，這絕不是?個好算法，因為鬼知道它要運行多久才有結果。

技術崗筆試面試考的那些算法題，求個最大值最小值什么的，你怎么求？必須得把所有可行解窮舉出來才能找到最值對吧，說白了不就這么點事兒么。

但是，你千萬不要覺得窮舉這個事兒很簡單，窮舉有兩個關鍵難點：無遺漏、無冗余。

遺漏，會直接導致答案出錯；冗余，會拖慢算法的運?速度。所以，當你看到?道算法題，可以從這兩個維度去思考：

1. 如何窮舉？即?遺漏地窮舉所有可能解。
2. 如何聰明地窮舉？即避免所有冗余的計算，消耗盡可能少的資源求出答案。

不同類型的題目，難點是不同的，有的題目難在「如何窮舉」，有的題目難在「如何聰明地窮舉」。

什么算法的難點在「如何窮舉」呢？一般是遞歸類問題，最典型的就是動態規劃系列問題。

后文 動態規劃核心套路 闡述了動態規劃系列問題的核心原理，無非就是先寫出暴力窮舉解法（狀態轉移方程），加個備忘錄就成自頂向下的遞歸解法了，再改一改就成自底向上的遞推迭代解法了， 動態規劃的降維打擊 里也講過如何分析優化動態規劃算法的空間復雜度。

上述過程就是在不斷優化算法的時間、空間復雜度，也就是所謂「如何聰明地窮舉」。這些技巧一聽就會了，但很多讀者留言說明白了這些原理，遇到動態規劃題目還是不會做，因為想不出狀態轉移方程，第一步的暴力解法都寫不出來。

這很正常，因為動態規劃類型的題目可以千奇百怪，找狀態轉移方程才是難點，所以才有了 動態規劃設計方法：數學歸納法 這篇文章，告訴你遞歸窮舉的核心是數學歸納法，明確函數的定義，然后利用這個定義寫遞歸函數，就可以窮舉出所有可行解。

什么算法的難點在「如何聰明地窮舉」呢？一些耳熟能詳的非遞歸算法技巧，都可以歸在這一類。

比如后文 Union Find 并查集算法詳解 告訴你一種高效計算連通分量的技巧，理論上說，想判斷兩個節點是否連通，我用 DFS/BFS 暴力搜索（窮舉）肯定可以做到，但人家 Union Find 算法硬是用數組模擬樹結構，給你把連通性相關的操作復雜度給干到 O(1) 了。

這就屬于聰明地窮舉，大佬們把這些技巧發明出來，你學過就會用，沒學過恐怕很難想出這種思路。

再比如貪心算法技巧，后文 當老司機學會貪心算法 就告訴你，所謂貪心算法就是在題目中發現一些規律（專業點叫貪心選擇性質），使得你不用完整窮舉所有解就可以得出答案。

人家動態規劃好歹是無冗余地窮舉所有解，然后找一個最值，你貪心算法可好，都不用窮舉所有解就可以找到答案，所以后文 貪心算法解決跳躍游戲 中貪心算法的效率比動態規劃還高。

再比如大名鼎鼎的 KMP 算法，你寫個字符串暴力匹配算法很容易，但你發明個 KMP 算法試試？KMP 算法的本質是聰明地緩存并復用一些信息，減少了冗余計算，后文 KMP 字符匹配算法 就是使用狀態機的思路實現的 KMP 算法。

本文轉載至：labuladong 的算法小抄