動態規劃和貪心的本質區別是什麼？

01-11

我只是突然發現知乎上居然沒人問過這個問題，是因為這問題太簡單了么。。我想聽聽大家都是怎麼想的。。最近先學dp，學了一段時間覺得好像有個模子了，但是一學貪心又有點暈暈的了。。

某種程度上，動規是貪心的泛化，貪心是動規的特例。

動規：大爆搜

貪心：把大爆搜剪枝剪到只有一條

（大霧

我嘗試用一個最近我琢磨的動態規劃問題作為例子解釋一下，看看能不能幫到題主。由於沒怎麼正經學過演算法，如果答案中有什麼不對的地方，懇請各位路過的朋友批評指正，我好「聞過裝喜」。

這個問題叫做 Bitonic euclidean salesman 問題（《演算法導論》一書動態規劃一章後面的習題）。考慮平面直角坐標繫上的 n 個點（n &>= 2），它們的橫坐標兩兩不同。假如我想這樣經過所有這些點：

先從最左邊一個點出發，以直線段連接其中一部分點，到達最右邊一個點。
再從最右邊一個點出發，以直線段連接剩下的點，到達最左邊一個點。

這種遍歷的方式，叫做 Bitonic 的（雙調的，即兩次單調之和）。要求找到滿足上述方式而構成的直線段環路中最短的。

由於常年是一個糊塗蟲，我一上來就把問題想簡單了。將這些點從左到右記為 P_0, P_1, ..., P_{n - 1}，考慮前 k 個點加上最後一個點組成的環路。這些點中，肯定有一部分在最優環路的從左到右的那部分（記為 L2R），而另一部分在最優環路的從右到左部分（記為 R2L）。（當然，由於對稱性，L2R 和從 R2L 可以互換。以及，兩端的兩個點，我們認為既不屬於 L2R，也不屬於 R2L。）現在考慮第 k + 1 個點，即 P_{k}。我肯定得把它加到 L2R 或 R2L 中。那麼，我當然選擇其一，使得新行程 L2R 和 R2L 的長度總和最小啦。這樣做，我其實考慮的只是「眼前利益」，這種做法就是所謂「貪心」的。

很遺憾，在這個問題上，「貪心」的做法是得不到全局最優解的。因為，我沒有考慮，將 P_{k} 加入的時候，之前已經決定好的 L2R 和 R2L 是否需要做出改變。這一點不難找到反例，如 n = 5，各點分別為 (0, 0), (1, 2), (2, 1), (3, 5), (4, 0)。當 k = 3 時，我們只是沒有考慮 (3, 5) 這個點，另外 4 個點構成的最優環路中，

L2R = (0, 0) --&> (1, 2) --&> (2, 1) --&> (4, 0) 以及 R2L = (0, 0) &<-- (4, 0)。

這個結論通過窮舉就不難得到。但我們加入第 k + 1 個點 (3, 5)，再通過窮舉可以發現，新形成的最優環路中，

L2R = (0, 0) --&> (1, 2) --&> (3, 5) --&> (4, 0) 以及 R2L = (0, 0) &<-- (2, 1) &<-- (4, 0)。

這裡帶上左右端點，顯得清楚一點。也就是說，我們把 P_k = (3, 5) 這個點加入 L2R 的時候，需要把 (2, 1) 挪到 R2L 中去，才能保證新形成的環路的最優性。這就使得「貪心」的計劃破產了。

用動態規劃來解決這個問題可能有不止一種辦法。例如，我們維護幾個數組：

L[1 .. n - 2, 0 .. n - 2]
second_right_most_L2R[0 .. n - 1]
right_most_R2L[0 .. n - 1]

除左右端點外，將剩餘的點即 P_1, P_2, ..., P_{n - 1} 從做到右遍歷一次。通過適當的計算，使得遍歷經過 P_i 之後，對 j &<= i：

L[i, j] 記住的是 P_0, P_1, ..., P_i 以及 P_{n - 1} 組成，且 L2R 部分的最右點為 P_j 的最優環路的長度；
second_right_most_L2R[j] 是這條環路 L2R 部分次右點的編號；
right_most_R2L[j] 是這條環路 R2L 部分最右點的編號。

不論是 L，還是剩下那倆倒霉催的數組，其實維護的都是遍歷經過某個點時的「狀態」。維護了這些「狀態」（或者說，擴充了問題本身能直接看出來的那些「狀態」），就能讓問題呈現出「最優子結構」，即子問題的最優解經過適當的計算能得到母問題的最優解。這種計算方式，由於不僅僅是看「眼前利益」，還利用了記錄了「歷史」的「狀態」們，就不再是「貪心」的。

謝邀。

貪心是求局部最優，以得到全局最優（不一定是正確的，需要證明）

dp是通過一些狀態來描述一些子問題，然後通過狀態之間的轉移來求解（一般只要轉移方程是正確的，答案必然是正確的）

拿到一個問題，首先要做的是分析，大致分析過程如下圖：

這圖是演算法老師課程的精髓，有點兒不清，暫時先擱這兒，等下重新畫一下。

從圖中可以看出分治、動規、貪心三者的關係。

分治：對於組合最優化模型，考慮是否可分成獨立子問題，如果可以則可以考慮將問題分成更小的子問題，分別處理後再merge。

動態規劃：動態規劃與分治非常像，都是要把大問題分解，然後再將小問題的解合併起來得到大問題的解。動態規劃一般會枚舉所有的子問題，把所有子問題都解決一遍，但通過生成一張記錄子問題值得表來減少重複計算，大大降低複雜度。動規要求最優子結構

------太困了沒答完感覺知識忘了不少先佔個坑周末複習好了補上

貪心：A最優+B最優

動態規劃：（A+B）最優

就單步而言

貪心的A最優是前一步的結果，B最優需要遍歷找到

動態規劃的A為前一步的可行解，需要選擇一個B後再去找A

貪心著眼現實當下，動規謹記歷史進程。

舉個栗子：

拿囚徒困境來看，

貪心演算法類似多個零和博弈，就是A選擇背叛，繼而B選擇背叛；

動態規劃是綜合博弈，我在A的可選範圍內，找到兩人整體最優解，即都不背叛。

簡單地來說：貪心只選擇當前最有利的，不考慮這步選擇對以後的選擇造成的影響，眼光短淺，不能看出全局最優；動規是通過較小規模的局部最優解一步步最終得出全局最優解。

動態規劃本質上是窮舉法，只是不重複計算罷了。結果是最優的。複雜度高。

貪心演算法一般不是最優的。複雜度一般低。

只做大自然的搬運工動態規劃與貪心演算法的區別與聯繫 - 一顆賽艇 - 博客頻道 - CSDN.NET

動態規劃是把問題分成儘可能多的相同的子問題，分治演算法是把問題儘可能多的分成獨立的子問題。