1樓：CRIMX
兩者相似的地方在於技巧性地設計子問題。
動態規劃希望復用子問題的解，最好被反覆依賴。其本質還是窮舉，所以當前並不知道哪個子問題的解會構成最終最優解。但知道這個子問題可能會被反覆計算，所以把結果快取起來。
整個過程是樹狀的搜尋過程。
貪心希望每次都能排除一堆子問題。它不需要復用子問題的解，當前最優解從子問題最優解即可得出。整個過程是線性的推導過程。
2樓：肥貓加菲
我嘗試用乙個最近我琢磨的動態規劃問題作為例子解釋一下，看看能不能幫到題主。由於沒怎麼正經學過演算法，如果答案中有什麼不對的地方，懇請各位路過的朋友批評指正，我好「聞過裝喜」。
這個問題叫做 Bitonic euclidean salesman 問題（《演算法導論》一書動態規劃一章後面的習題）。考慮平面直角座標系上的 n 個點（n >= 2），它們的橫座標兩兩不同。假如我想這樣經過所有這些點：
先從最左邊乙個點出發，以直線段連線其中一部分點，到達最右邊乙個點。
再從最右邊乙個點出發，以直線段連線剩下的點，到達最左邊乙個點。
這種遍歷的方式，叫做 Bitonic 的（雙調的，即兩次單調之和）。要求找到滿足上述方式而構成的直線段環路中最短的。
由於常年是乙個糊塗蟲，我一上來就把問題想簡單了。將這些點從左到右記為 P_0, P_1, ..., P_，考慮前 k 個點加上最後乙個點組成的環路。
這些點中，肯定有一部分在最優環路的從左到右的那部分（記為 L2R），而另一部分在最優環路的從右到左部分（記為 R2L）。（當然，由於對稱性，L2R 和從 R2L 可以互換。以及，兩端的兩個點，我們認為既不屬於 L2R，也不屬於 R2L。
）現在考慮第 k + 1 個點，即 P_。我肯定得把它加到 L2R 或 R2L 中。那麼，我當然選擇其一，使得新行程 L2R 和 R2L 的長度總和最小啦。
這樣做，我其實考慮的只是「眼前利益」，這種做法就是所謂「貪心」的。
很遺憾，在這個問題上，「貪心」的做法是得不到全域性最優解的。因為，我沒有考慮，將 P_ 加入的時候，之前已經決定好的 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_ 從做到右遍歷一次。通過適當的計算，使得遍歷經過 P_i 之後，對 j <= i：
L[i, j] 記住的是 P_0, P_1, ..., P_i 以及 P_ 組成，且 L2R 部分的最右點為 P_j 的最優環路的長度；
second_right_most_L2R[j] 是這條環路 L2R 部分次右點的編號；
right_most_R2L[j] 是這條環路 R2L 部分最右點的編號。
不論是 L，還是剩下那倆倒霉催的陣列，其實維護的都是遍歷經過某個點時的「狀態」。維護了這些「狀態」（或者說，擴充了問題本身能直接看出來的那些「狀態」），就能讓問題呈現出「最優子結構」，即子問題的最優解經過適當的計算能得到母問題的最優解。這種計算方式，由於不僅僅是看「眼前利益」，還利用了記錄了「歷史」的「狀態」們，就不再是「貪心」的。
3樓：素履
舉個栗子：
拿囚徒困境來看，
貪心演算法類似多個零和博弈，就是A選擇背叛，繼而B選擇背叛；
動態規劃是綜合博弈，我在A的可選範圍內，找到兩人整體最優解，即都不背叛。
4樓：
簡單地來說：貪心只選擇當前最有利的，不考慮這步選擇對以後的選擇造成的影響，眼光短淺，不能看出全域性最優；動規是通過較小規模的區域性最優解一步步最終得出全域性最優解。
5樓：
貪心：A最優+B最優
動態規劃：（A+B）最優
就單步而言
貪心的A最優是前一步的結果，B最優需要遍歷找到動態規劃的A為前一步的可行解，需要選擇乙個B後再去找A
營銷和銷售的本質區別是什麼？
乙個公司可以沒有營銷，但是必須要有銷售，這是本質區別之一。營銷的目的是傳遞，銷售的目的是交易，這是本質區別之二。營銷做好了會提公升品牌價值，銷售做好了會提公升品牌業績，這是區別之三。舉個形象點的例子。一家賣奶茶的。營銷就是讓更多人知道，銷售就只需要讓知道它的人買 二者重合的部分就不多說了。其實說了這...
isfj和istj的本質區別是什麼？
判斷功能的不同，雖然感知功能一致，但是判斷功能乙個是te乙個是fe，還是差別很大的。isfj關注群體和諧，有自己的一套道德標準，會看似溫柔實則固執的限制周圍的人，優點就是高階isfj足夠堅韌足夠忠誠，但是更多的是習慣佔據道德制高點，時常覺得自己道德上沒有可指責的地方，口頭禪就是 我都是為了你好 實際...
微觀和巨集觀的本質區別是什麼？
魯新奎 任何巨集觀物體都是由微觀粒子構成的，微觀是巨集觀的本原和本源，微觀物理世界的規律才是巨集觀世界的本質規律。巨集觀是由微觀復合疊加而成的，巨集觀的恆定和連續都是由週期性波動 分立性 間斷性的微觀量子現象復合疊加而成的假象。但人類最先了解的是巨集觀的恆定和連續假象，經想象和腦補及理想化假設就形成...