【算法導論】貪心算法，遞歸算法，動态規劃算法總結

一般實際生活中我們遇到的算法分為四類：

一>判定性問題

二>最優化問題

三>構造性問題

四>計算性問題

而今天所要總結的算法就是着重解決 最優化問題

《算法之道》對三種算法進行了歸納總結，如下表所示：

<col>

标準分治

動态規劃

貪心算法

适用類型

通用問題

優化問題

子問題結構

每個子問題不同

很多子問題重複（不獨立）

隻有一個子問題

最優子結構

不需要

必須滿足

子問題數

全部子問題都要解決

隻要解決一個子問題

子問題在最優解裡

全部

部分

選擇與求解次序

先選擇後解決子問題

先解決子問題後選擇

分治算法特征：

1）規模如果很小，則很容易解決。//一般問題都能滿足

2）大問題可以分為若幹規模小的相同問題。//前提

3）利用子問題的解，可以合并成該問題的解。//關鍵

4）分解出的各個子問題互相獨立，子問題不再包含公共子問題。 //效率高低

【一】動态規劃：

依賴：依賴于有待做出的最優選擇

實質：就是分治思想和解決備援。

自底向上（每一步，根據政策得到一個更小規模的問題。最後解決最小規模的問題。得到整個問題最優解）

特征：動态規劃任何一個i+1階段都僅僅依賴 i 階段做出的選擇。而與i之前的選擇無關。但是動态規劃不僅求出了目前狀态最優值，而且同時求出了到中間狀态的最優值。

缺點：空間需求大。

【二】貪心算法：

依賴：依賴于目前已經做出的所有選擇。

自頂向下（就是每一步，根據政策得到一個目前最優解。傳遞到下一步，進而保證每一步都是選擇目前最優的。最後得到結果）

【三】分治算法：

實質：遞歸求解

缺點：如果子問題不獨立，需要重複求公共子問題