算法基本思想(結尾附上記憶口訣)

• 貪心
• 分治
• 枚舉
• 動態
• 回溯
• 遞歸（兄弟思想-遞推）

這篇文章說的這些思想網上一大堆,可以不看。直接關注結尾自創口訣，希望給你提供一點幫助。

遞歸

概述

在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法

特點

1. 邊界條件
2. 規模遞減

能解決的問題

1. 數據的定義是按遞歸定義的。如Fibonacci函數。
2. 問題解法按遞歸算法實現。如Hanoi問題。
3. 數據的結構形式是按遞歸定義的。如二叉樹、廣義表等

遞歸解題的基本套路

1. 明確這個函數的功能
2. 遞推公式 自上而下的分析
3. 補充到步驟1中定義的函數中
4. 時間復雜度的計算

參考文獻

一文看懂什么遞歸（算法小結）
https://zhuanlan.zhihu.com/p/94748605
https://juejin.im/post/6844904008595816462

分治

概述

在計算機科學中，分治法是建基于多項分支遞歸的一種很重要的算法范式。字面上的解釋是"分而治之"，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并

步驟

分解（將原問題分解成一系列子問題）
求解（遞歸的求解各子問題，若子問題足夠小，則直接求解）
合并（將子問題的解合并成原問題的解）

適用情況

如排序算法（歸并排序、快速排序）、傅立葉變換（快速傅立葉變換）

貪心

概述

又稱貪婪算法，是一種在每一步選擇中都采取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是最好或最優的算法。[1]比如在旅行推銷員問題中，如果旅行員每次都選擇最近的城市，那這就是一種貪心算法。
貪心算法在有最優子結構的問題中尤為有效。最優子結構的意思是局部最優解能決定全局最優解。簡單地說，問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解。
貪心算法與動態規劃的不同在于它對每個子問題的解決方案都做出選擇，不能回退。動態規劃則會保存以前的運算結果，并根據以前的結果對當前進行選擇，有回退功能。

貪心算法的基本思路

1. 根據問題來建立數學模型，一般面試題會定義一個簡單模型；
2. 把待求解問題劃分成若干個子問題，對每個子問題進行求解，得到子問題的局部最優解；
3. 把子問題的局部最優解進行合并，得到最后基于局部最優解的一個解，即原問題的答案。

具有以下性質可以使用貪心算法
最優子結構
貪心選擇性質

適用情況

貪心法可以解決一些最優化問題，如：求圖中的最小生成樹、求哈夫曼編碼……對于其他問題，貪心法一般不能得到我們所要求的答案。一旦一個問題可以通過貪心法來解決，那么貪心法一般是解決這個問題的最好辦法。由于貪心法的高效性以及其所求得的答案比較接近最優結果，貪心法也可以用作輔助算法或者直接解決一些要求結果不特別精確的問題。在不同情況，選擇最優的解，可能會導致辛普森悖論（Simpson’s Paradox），不一定出現最優的解。

貪心算法在Data Science領域都被資泛應用，特別是金融工程。其中一個貪心算法例子就是Ensemble method

實例

最小生成樹、求哈夫曼編碼、活動選擇問題

回溯

概述

回溯法:有"通用的解題法"之稱，可以系統地搜索一個問題的所有解或任一解。在包含問題的所有解的解空間樹時，按照深度優先的策略，從根節點觸發搜索解空間樹。搜索至任一結點時，總是先判斷該結點是否肯定不包含問題的解，如果不包含，則跳過對以該結點為根的子樹的搜索，逐層向其祖先結點回溯;否則，進入該子樹，繼續按深度優先的策略進行搜索。

可以理解為先進行深度優先搜索，一直向下探測，當此路不通時，返回上一層探索另外的分支，重復此步驟，這就是回溯，意為先一直探測，當不成功時再返回上一層。

適用情況

實例

八皇后問題、迷宮類問題

枚舉

概述

枚舉算法的思想是：將問題的所有可能的答案一一列舉，然后根據條件判斷此答案是否合適，保留合適的，丟棄不合適的。

解題思路

確定枚舉對象、枚舉范圍和判定條件。
逐一列舉可能的解，驗證每個解是否是問題的解。

動態

概述

動態規劃在查找有很多重疊子問題的情況的最優解時有效。它將問題重新組合成子問題。為了避免多次解決這些子問題，它們的結果都逐漸被計算并被保存，從簡單的問題直到整個問題都被解決。因此，動態規劃保存遞歸時的結果，因而不會在解決同樣的問題時花費時間。
動態規劃只能應用于有最優子結構的問題。最優子結構的意思是局部最優解能決定全局最優解（對有些問題這個要求并不能完全滿足，故有時需要引入一定的近似）。簡單地說，問題能夠分解成子問題來解決。

適用情況

1. 最優子結構性質。如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理）。最優子結構性質為動態規劃算法解決問題提供了重要線索。
2. 無后效性。即子問題的解一旦確定，就不再改變，不受在這之后、包含它的更大的問題的求解決策影響。
3. 子問題重疊性質。子問題重疊性質是指在用遞歸算法自頂向下對問題進行求解時，每次產生的子問題并不總是新問題，有些子問題會被重復計算多次。動態規劃算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然后將其計算結果保存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地查看一下結果，從而獲得較高的效率，降低了時間復雜度。

實例

0-1背包問題、最長公共子序列

記憶口訣

貪心小蔡，

分治灣灣，

枚人行動，

灣灣回歸。

(關注:魯班曰)