分治演算法包括

1. 分治、貪心五大演算法

1、分治
分治（即分而治喊孫之），把一個復雜的問題分成多鄭激鏈個相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合並。
適用場景：二分搜索、歸並排序、快速排序、大整數乘法、第K小元素、最近點對、快速傅里葉變換等。

2、動態規劃
動態規劃法也是把問題一層一層地分解為規模逐漸減小的同類型的子問題。動態規劃通常用來求最優化問題。此類問題可以有很多可行解，我們求出的是一個最優解，可能存在多個最優解。（最優子結構、公共子問題）
與分治法的區別是：分治的子問題是相互獨立的，動態規劃最好解決有公共子問題的，子問題相關性很大。
使用場景：矩陣連乘、鋼條切割、最長公共子序列、最優二叉搜索樹、流水作業調度、0/1背包問題等。

維特比演算法是動態規劃在HMM中的應用，維特比演算法用於解決HMM的預測或者叫解碼問題。
viterbi有最優解是因為HMM每一步是條件獨立的！既然後面的概率和前面的沒關系，那前面選最大的概率就行了。
而beam search時後面的概率依賴於前面所有的詞，相當於n-gram是滿的，viterbi的n-gram是2

背包問題：
https://blog.csdn.net/wind__chaser/article/details/89457771
https://blog.csdn.net/qq_38410730/article/details/81667885

3、貪心
通過局部最優選擇達鉛吵到全局最優選擇。貪心演算法不一定總產生最優解，貪心演算法是否產生優化解，需嚴格證明貪心演算法產生最優解的條件：（最優子結構、貪心選擇性）
貪心選擇性：當一個問題的全局最優解可以通過局部最優解得到，稱這個問題具有貪心選擇性。
適用場景：活動選擇問題、哈夫曼編碼問題、最小生成樹問題、單源最短路徑問題等。

貪心演算法：softmax之後取最大概率。與之對應的是，Beam Search演算法
http://www.360doc.com/content/18/0618/09/17563728_763230413.shtml
https://blog.csdn.net/qq_16234613/article/details/83012046
https://www.hu.com/question/54356960

分治和動態規劃的區別：
動態規劃也是一種分治思想（比如其狀態轉移方程就是一種分治），但與分治演算法不同的是，分治演算法是把原問題分解為若干個子問題，
自頂向下求解子問題，合並子問題的解，從而得到原問題的解。動態規劃也是把原始問題分解為若干個子問題，然後自底向上，
先求解最小的子問題，把結果存在表格中，在求解大的子問題時，直接從表格中查詢小的子問題的解，避免重復計算，從而提高演算法效率。

動態規劃和分治法有些相像，都是把一個問題分成了很多子問題來求解，但是不同的是動態規劃會記憶之前解決的子問題的結果，
避免了重復計算。判斷一個問題是否能用動態規劃求解，要看它是否能劃分成合適的子問題，然後寫出遞推關系式。
動態規劃得到的解一定是最優解。

2. 分治演算法幾個經典例子

分治法，字面意思是「分而治之」，就是把一個復雜的1問題分成兩個或多個相同或相似的子問題，再把子問題分成更小的子問題直到最後子問題可以簡單地直接求解，原問題的解即子問題的解的合並，這個思想是很多高效演算法的基礎。

圖二

大整數乘法

Strassen矩陣乘法

棋盤覆蓋

合並排序

快速排序

線性時間選擇

最接近點對問題

循環賽日程表

漢諾塔

3. 每天一個知識點：分治演算法：選擇問題

選擇問題的要求是找出含有 N 個元素的表 S 中的第 k 個最小的元素。

基本的演算法是簡單的遞歸策略。設 N 大於截止點(cutoff point)，在截止點後元素將進行簡單的排序，v 是選出的一個元素，叫做樞紐元(pivot)。其餘的元素被放在兩個集合 和 中。 含有那些不大於 v 的元素，而 則包含那些不小於 v 的元素。

為了得到一個線性演算法，必須保證子問題只是原問題的一部分，而不僅僅只是比原問題少幾個元素。這里要解決問題就是如何花費更少的時間來尋找樞紐元。

為得到一個好的最壞情形，關鍵想法是再用一個間接層。不是從隨機元素的樣本中找出中項，而是從中項的樣本中找出中項。

基本的樞紐元選擇演算法如下：

上面給出的樞紐元選擇法，有一個專業的術語，叫做「五分化中項的中項」。「五分化中項的中項」保證每個遞歸子問題的大小最多是原問題的大約 70%。對於整個選擇演算法，樞紐元可以足夠快的算出，以確保 的運行時間。

定理：使用「五分化中項的中項」的快速選擇演算法的運行時間為 。

分治演算法還可以用來降低演算法預計所需要的比較次數。

設有 N 個數的集合 S 並且要尋找其中第 k 個最小的數 X。我們選擇 S 的子集 S『，令 δ 是某個數，使得計算過程所用的平均比較次數最小化。

找出 S』 中第 ( ) 個和第 個最小的元素，幾乎可以肯定 S 中的第 k 個元素將落在 和 之間，此時，問題變成了 2δ 個元素的選擇問題。

經過分析，會發現，若 和 ，則期望的比較次數為 ，除低次項外它是最優的。（如果 k>N/2，那麼我們可以考慮查找第(N-k)個最大元素的對稱問題。）

最後一項代表進行兩次選擇以確定 和 的代價。假設採用合理聰明的策略，則劃分的平均代價等於 N 加上 在 S 中的期望階(expected rank)，即 。如果第 k 個元素在 S『 中出現，那麼代價就是 O(N)。然而，s 和 δ 已經被選取以保證這種情況以非常低的概率 o(1/N) 發生，因此該可能性的期望代價是 o(1)，當它的 N 越來越大時趨向於 0。

這個分析指出，找出中項平均大約需要 1.5N 次比較。當然，該演算法為計算 s 需要浮點運算，這在一些機器上可能使該演算法減慢速度。不過即使是這樣，若能正確實現，則該演算法完全能夠比得上快速選擇實現方法。

4. 程序員都應該精通的六種演算法，你會了嗎

對於一名優秀的程序員來說，面對一個項目的需求的時候，一定會在腦海里浮現出最適合解決這個問題的方法是什麼，選對了演算法，就會起到事半功倍的效果，反之，則可能會使程序運行效率低下，還容易出bug。因此，熟悉掌握常用的演算法，是對於一個優秀程序員最基本的要求。

那麼，常用的演算法都有哪些呢？一般來講，在我們日常工作中涉及到的演算法，通常分為以下幾個類型：分治、貪心、迭代、枚舉、回溯、動態規劃。下面我們來一一介紹這幾種演算法。

一、分治演算法

分治演算法，顧名思義，是將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

分治演算法一般分為三個部分：分解問題、解決問題、合並解。

分治演算法適用於那些問題的規模縮小到一定程度就可以解決、並且各子問題之間相互獨立，求出來的解可以合並為該問題的解的情況。

典型例子比如求解一個無序數組中的最大值，即可以採用分治演算法，示例如下：

def pidAndConquer(arr,leftIndex,rightIndex):

if(rightIndex==leftIndex+1 || rightIndex==leftIndex){

return Math.max(arr[leftIndex],arr[rightIndex]);

}

int mid=(leftIndex+rightIndex)/2;

int leftMax=pidAndConquer(arr,leftIndex,mid);

int rightMax=pidAndConquer(arr,mid,rightIndex);

return Math.max(leftMax,rightMax);

二、貪心演算法

貪心演算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。

貪心演算法的基本思路是把問題分成若干個子問題，然後對每個子問題求解，得到子問題的局部最優解，最後再把子問題的最優解合並成原問題的一個解。這里要注意一點就是貪心演算法得到的不一定是全局最優解。這一缺陷導致了貪心演算法的適用范圍較少，更大的用途在於平衡演算法效率和最終結果應用，類似於：反正就走這么多步，肯定給你一個值，至於是不是最優的，那我就管不了了。就好像去菜市場買幾樣菜，可以經過反復比價之後再買，或者是看到有賣的不管三七二十一先買了，總之最終結果是菜能買回來，但搞不好多花了幾塊錢。

典型例子比如部分背包問題：有n個物體，第i個物體的重量為Wi，價值為Vi，在總重量不超過C的情況下讓總價值盡量高。每一個物體可以只取走一部分，價值和重量按比例計算。

貪心策略就是，每次都先拿性價比高的，判斷不超過C。

三、迭代演算法

迭代法也稱輾轉法，是一種不斷用變數的舊值遞推新值的過程。迭代演算法是用計算機解決問題的一種基本方法，它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令(或一定步驟)進行重復執行，在每次執行這組指令(或這些步驟)時，都從變數的原值推出它的一個新值。最終得到問題的結果。

迭代演算法適用於那些每步輸入參數變數一定，前值可以作為下一步輸入參數的問題。

典型例子比如說，用迭代演算法計算斐波那契數列。

四、枚舉演算法

枚舉演算法是我們在日常中使用到的最多的一個演算法，它的核心思想就是:枚舉所有的可能。枚舉法的本質就是從所有候選答案中去搜索正確地解。

枚舉演算法適用於候選答案數量一定的情況。

典型例子包括雞錢問題，有公雞5，母雞3，三小雞1，求m錢n雞的所有可能解。可以採用一個三重循環將所有情況枚舉出來。代碼如下：

五、回溯演算法

回溯演算法是一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就「回溯」返回，嘗試別的路徑。

許多復雜的，規模較大的問題都可以使用回溯法，有「通用解題方法」的美稱。

典型例子是8皇後演算法。在8 8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問一共有多少種擺法。

回溯法是求解皇後問題最經典的方法。演算法的思想在於如果一個皇後選定了位置，那麼下一個皇後的位置便被限制住了，下一個皇後需要一直找直到找到安全位置，如果沒有找到，那麼便要回溯到上一個皇後，那麼上一個皇後的位置就要改變，這樣一直遞歸直到所有的情況都被舉出。

六、動態規劃演算法

動態規劃過程是：每次決策依賴於當前狀態，又隨即引起狀態的轉移。一個決策序列就是在變化的狀態中產生出來的，所以，這種多階段最優化決策解決問題的過程就稱為動態規劃。

動態規劃演算法適用於當某階段狀態給定以後，在這階段以後的過程的發展不受這段以前各段狀態的影響，即無後效性的問題。

典型例子比如說背包問題，給定背包容量及物品重量和價值，要求背包裝的物品價值最大。