動(dòng)態(tài)規(guī)劃和貪心算法都是用來求最優(yōu)化問題，且二者都必須具有最有子結(jié)構(gòu)。貪心算法可以解決的問題，動(dòng)態(tài)規(guī)劃都能解決，可以說，貪心算法是動(dòng)態(tài)規(guī)劃的一個(gè)特例。

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

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃）與分治法相似，都是通過組合子問題的解來求解原問題。分治法將問題劃分為互不相交的子問題，遞歸求解子問題，再將它們的解組合起來，求出原問題的解。與之相反，動(dòng)態(tài)規(guī)劃應(yīng)用于子問題重疊的情況，即不同的子問題具有公共的子子問題（子問題的求解釋遞歸進(jìn)行的，將其劃分為更小的子子問題）。這種情況下，動(dòng)態(tài)規(guī)劃對(duì)公共子子問題只求一次解，而分治法會(huì)反復(fù)求解公共子子問題。

我們通常按如下四個(gè)步驟來設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法：

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

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

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

利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解。

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

貪心算法

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

可以按如下步驟 設(shè)計(jì)貪心算法：

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

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

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

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

這也是貪心算法與動(dòng)態(tài)規(guī)劃的不同之處。在動(dòng)態(tài)規(guī)劃方法中，每個(gè)步驟都要進(jìn)行一次選擇，但選擇通常依賴于子問題的解。因此，我們通常以一種自底向上的方式求解動(dòng)態(tài)規(guī)劃問題，先求解嬌小的子問題，然后是交大的子問題（我們也可以自頂向下求解，但需要備忘機(jī)制。當(dāng)然，即使算法是自頂向下進(jìn)行計(jì)算，我們?nèi)匀恍枰惹蠼庾訂栴}再進(jìn)行選擇）。在貪心算法中，我們總是做出當(dāng)時(shí)看來最佳的選擇，然后求解剩下的唯一子問題。貪心算法進(jìn)行選擇時(shí)可能依賴于之前做出的選擇，但不依賴于任何將來的選擇或是子問題的解。因此，與動(dòng)態(tài)規(guī)劃先求解子問題才能進(jìn)行第一次選擇不用，貪心算法在進(jìn)行第一次選擇之前不求解任何子問題。一個(gè)動(dòng)態(tài)規(guī)劃算法是自底向上進(jìn)行計(jì)算的，而一個(gè)貪心算法通常是自頂向下的，進(jìn)行一次又一次選擇，將給定問題實(shí)例變得更小。

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

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

一、背包相關(guān)問題

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

解法：只關(guān)心數(shù)量多，便把重量從小到大排序，依次選，直到裝不下。

二、區(qū)間相關(guān)問題

1.選擇不相交區(qū)間：數(shù)軸上有N個(gè)開區(qū)間(Li,Ri)，請(qǐng)選擇盡量多個(gè)區(qū)間，并保證這些區(qū)間兩兩沒有公共點(diǎn)。

三、Huffman編碼

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