分治法，動態規劃及貪心演算法區別

分治法，動態規劃法，貪心演算法這三者之間有類似之處，比如都需要將問題劃分為一個個子問題，然後通過解決這些子問題來解決最終問題。但其實這三者之間的區別還是很大的。

1.分治法

分治法(Divide-and-Conquer) : 將原問題劃分成n個規模較小而結構與原問題相似的子問題；遞歸地解決這些子問題，然後再合併其結果，就得到原問題的解。

分治模式在每一層遞歸上都有三個步驟：

• 分解(Divide)：將原問題分解成一系列子問題；
• 解決(Conquer)：遞歸地解決各個子問題。若子問題足夠小，則直接求解。
• 合併(Combine)：將子問題的結果合併成原問題的解。

合併排序(Merge Sort)是一個典型分治法的例子。其對應的直觀的操作如下:

分解： 將n個元素分成各含n/2個元素的子序列；

解決：用合併排序法對兩個子序列遞歸地排序；

合併：合併兩個已排序的子序列以得到排序結果。

2. 動態規劃法

動態規劃演算法的設計可以分為如下4個步驟：

• 描述最優解的結構
• 遞歸定義最優解的值
• 按自底向上的方式計算最優解的值
• 由計算出的結果構造一個最優解

分治法是指將問題劃分成一些獨立的子問題，遞歸的求解各子問題，然後合併子問題的解而得到原問題的解。與此不同，動態規劃適用於子問題獨立且重疊的情況，也就是各子問題包含公共的子子問題。在這種情況下，若用分治法則會做許多不必要的工作，即重複地求解公共的子問題。動態規劃演算法對每個子子問題只求解一次，將其結果保存在一張表中，從而避免每次遇到各個子問題時重新計算答案。

適合採用動態規劃方法的最優化問題中的兩個要素：最優子機構和重疊子問題。

最優子機構：如果問題的一個最優解中包含了子問題的最優解，則該問題具有最優子機構。

重疊子問題：適用於動態規劃求解的最優化問題必須具有的第二個要素是子問題的空間要很小，也就是用來求解原問題的遞歸演算法反覆地解同樣的子問題，而不是總是在產生新的子問題。對兩個子問題來說，如果它們確實是相同的子問題，只是作為不同問題的子問題出現的話，則它們是重疊的。

In a word, 分治法 —— 各子問題獨立；動態規劃 —— 各子問題重疊。

演算法導論： 動態規劃要求其子問題既要獨立又要重疊，這看上去似乎有些奇怪。雖然這兩點要求聽起來可能矛盾的，但它們描述了兩種不同的概念，而不是同一個問題的兩個方面。如果同一個問題的兩個子問題不共享資源，則它們就是獨立的。對兩個子問題倆說，如果它們確實是相同的子問題，只是作為不同問題的子問題出現的話，是重疊的，則它們是重疊

3. 貪心演算法

對許多最優化問題來說，採用動態規劃方法來決定最佳選擇有點「殺雞用牛刀」了，只要採用另一些更簡單有效的演算法就行了。貪心演算法是使所做的選擇看起來都是當前最佳的，期望通過所做的局部最優選擇來產生出一個全局最優解。貪心演算法對大多數優化問題來說能產生最優解，但也不一定總是這樣的。

貪心演算法只需考慮一個選擇（亦即，貪心的選擇）；在做貪心選擇時，子問題之一必須是空的，因此只留下一個非空子問題。

貪心演算法與動態規劃與很多相似之處。特別地，貪心演算法適用的問題也是最優子結構。貪心演算法與動態規劃有一個顯著的區別，就是貪心演算法中，是以自頂向下的方式使用最優子結構的。貪心演算法會先做選擇，在當時看起來是最優的選擇，然後再求解一個結果子問題，而不是先尋找子問題的最優解，然後再做選擇。

貪心演算法是通過做一系列的選擇來給出某一問題的最優解。對演算法中的每一個決策點，做一個當時看起來是最佳的選擇。這一點是貪心演算法不同於動態規劃之處。在動態規劃中，每一步都要做出選擇，但是這些選擇依賴於子問題的解。因此，解動態規劃問題一般是自底向上，從小子問題處理至大子問題。貪心演算法所做的當前選擇可能要依賴於已經做出的所有選擇，但不依賴於有待於做出的選擇或子問題的解。因此，貪心演算法通常是自頂向下地做出貪心選擇，不斷地將給定的問題實例歸約為更小的問題。貪心演算法劃分子問題的結果，通常是僅存在一個非空的子問題。

（本文轉自csdn博客，感謝原作者）