動態(tài)規(guī)劃和貪心算法都是用來求最優(yōu)化問題窘问，且二者都必須具有最有子結構。貪心算法可以解決的問題缸沃，動態(tài)規(guī)劃都能解決，可以說修械，貪心算法是動態(tài)規(guī)劃的一個特例趾牧。

貪心算法和動態(tài)規(guī)劃最大的不同在于，它并不是首先尋找子問題的最優(yōu)解肯污，然后在其中進行選擇翘单，而是首先做一次貪心選擇——在當時（局部）看來最有選擇——然后求解選出的子問題，從而不必費心求解所有可能相關的子問題仇箱。

動態(tài)規(guī)劃

動態(tài)規(guī)劃）與分治法相似县恕，都是通過組合子問題的解來求解原問題。分治法將問題劃分為互不相交的子問題剂桥，遞歸求解子問題忠烛，再將它們的解組合起來，求出原問題的解权逗。與之相反美尸，動態(tài)規(guī)劃應用于子問題重疊的情況，即不同的子問題具有公共的子子問題（子問題的求解釋遞歸進行的斟薇，將其劃分為更小的子子問題）师坎。這種情況下，動態(tài)規(guī)劃對公共子子問題只求一次解堪滨，而分治法會反復求解公共子子問題胯陋。

我們通常按如下四個步驟來設計一個動態(tài)規(guī)劃算法：

刻畫一個最優(yōu)解的結構特征（如果一個問題的最優(yōu)解包含其子問題的最優(yōu)解，就稱此問題具有最有子結構性質(zhì)）袱箱。

遞歸的定義最優(yōu)解的值遏乔。

計算最優(yōu)解的值，通常采用自底向上的方法发笔。

利用計算出的信息構造一個最優(yōu)解盟萨。

eg：最長公共子序列（LCS）問題。

貪心算法

求解最優(yōu)化問題的算法通常需要經(jīng)過一系列的步驟了讨，在每個步驟都面臨多種選擇捻激。對于許多最優(yōu)化問題，使用動態(tài)規(guī)劃算法求最優(yōu)解有些殺雞用牛刀了前计，可以使用更簡單更優(yōu)化的算法胞谭，即貪心算法（greedy algorithm）。它在每一步都做出當時看起來最佳的選擇男杈。也就是說韭赘，它總是做出局部最優(yōu)的選擇，寄希望這樣的選擇能導致全局最優(yōu)解势就。貪心算法并不保證得到最優(yōu)解泉瞻，但對很多問題確實可以求得最優(yōu)解。

可以按如下步驟 設計貪心算法：

將最優(yōu)化問題轉(zhuǎn)化為這樣的形式：對其作出一次選擇后苞冯，只剩下一個子問題需要求解袖牙。

證明作出貪心選擇后，原問題總是存在最優(yōu)解舅锄，即貪心選擇總是安全的鞭达。

證明作出貪心選擇后，剩余的子問題滿足性質(zhì)：其最優(yōu)解與貪心選擇組合即可得到原問題的最優(yōu)解皇忿，這樣就得到了最優(yōu)子結構畴蹭。

貪心選擇性質(zhì)（greedy-choice property）：我們可以通過作出局部最優(yōu)（貪心）選擇來構造全局最優(yōu)解。換句話說鳍烁，當進行選擇時叨襟，我們直接作出在當前問題中看來最優(yōu)的選擇，而不必考慮子問題的解幔荒。

這也是貪心算法與動態(tài)規(guī)劃的不同之處糊闽。在動態(tài)規(guī)劃方法中，每個步驟都要進行一次選擇爹梁，但選擇通常依賴于子問題的解右犹。因此，我們通常以一種自底向上的方式求解動態(tài)規(guī)劃問題姚垃，先求解嬌小的子問題念链，然后是交大的子問題（我們也可以自頂向下求解，但需要備忘機制积糯。當然掂墓，即使算法是自頂向下進行計算，我們?nèi)匀恍枰惹蠼庾訂栴}再進行選擇）絮宁。在貪心算法中梆暮，我們總是做出當時看來最佳的選擇，然后求解剩下的唯一子問題绍昂。貪心算法進行選擇時可能依賴于之前做出的選擇啦粹，但不依賴于任何將來的選擇或是子問題的解。因此窘游，與動態(tài)規(guī)劃先求解子問題才能進行第一次選擇不用唠椭，貪心算法在進行第一次選擇之前不求解任何子問題。一個動態(tài)規(guī)劃算法是自底向上進行計算的忍饰，而一個貪心算法通常是自頂向下的贪嫂，進行一次又一次選擇，將給定問題實例變得更小艾蓝。

eg：赫夫曼編碼力崇、最小生成樹算法（Kruskal算法和Prim算法）

幾個經(jīng)典貪心問題

一斗塘、背包相關問題

1.最優(yōu)裝載問題：給出N個物體，有一定重量亮靴。請選擇盡量多的物體馍盟，使總重量不超過C。

解法：只關心數(shù)量多茧吊，便把重量從小到大排序贞岭，依次選，直到裝不下搓侄。

二瞄桨、區(qū)間相關問題

1.選擇不相交區(qū)間：數(shù)軸上有N個開區(qū)間(Li,Ri)，請選擇盡量多個區(qū)間讶踪，并保證這些區(qū)間兩兩沒有公共點芯侥。

三、Huffman編碼

最優(yōu)編碼問題：給出N個字符的頻率 ci 俊柔，給每個字符賦予一個01編碼串筹麸，使得任意一個字符的編碼不是另一個字符編碼的前綴，而且編碼后總長度（每個字符的頻率與編碼長度乘積的總和）盡量小