很奇怪，動態(tài)規(guī)劃和貪心算法也有很多相似之處：
相同點：
0，兩者都用于求解最優(yōu)化問題
1，兩者都將待求解的問題分解成若干子問題
2，兩者都需要確定最優(yōu)子結(jié)構(gòu)，才能決定是否可以使用該方法
3，兩者都需要構(gòu)造遞歸式

最優(yōu)子結(jié)構(gòu)：一個問題的最優(yōu)解包含其子問題的最優(yōu)解

不同點：
1，動態(tài)規(guī)劃是自底向上計算，類似于將問題的規(guī)模從1開始，計算到n,其中i的求解依賴于i-1的結(jié)果；貪心算法則是自頂向下計算，選擇當(dāng)前一個最優(yōu)解，然后再看剩余問題的最優(yōu)解，一路剝削下去

2，動態(tài)規(guī)劃比貪心算法更加細(xì)致精確，貪心算法有時候求不出最優(yōu)解

貪心算法：面對規(guī)模為n的問題，每次選擇當(dāng)前情況的一個最優(yōu)解，然后在看剩余的n-1規(guī)模的問題。

貪心原則：最能符合問題需求的選擇

貪心算法需要論證
每次貪心選擇的解組合在一起就是最優(yōu)解 這個結(jié)論是否正確