動態規劃和貪心演算法都是一種遞推演算法，均用區域性最優解來推導全域性最優解，對於很多學習演算法的同學來說很是迷惑。那麼它們之間的區別究竟是什麼呢？且聽我慢慢道來
貪心演算法與動態規劃區別
貪心演算法：
1。貪心演算法中，作出的每步貪心決策都無法改變，因為貪心策略是由上一步的最優解推導下一步的最優解，而上一部之前的最優解則不作保留。 2。貪心法正確的條件是：每一步的最優解一定包含上一步的最優解。
動態規劃演算法：
1。全域性最優解中一定包含某個區域性最優解，但不一定包含前一個區域性最優解，因此需要記錄之前的所有最優解 。2。動態規劃的關鍵是狀態轉移方程，即如何由已求出的區域性最優解來推導全域性最優解。 3。邊界條件：即最簡單的，可以直接得出的區域性最優解。
貪心法的基本思路：
從問題的某一個初始解出發逐步逼近給定的目標，以儘可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。
該演算法存在問題：
1。 不能保證求得的最後解是最佳的； 2。 不能用來求最大或最小解問題； 3。 只能求滿足某些約束條件的可行解的範圍。
實現該演算法的過程：
從問題的某一初始解出發； while 能朝給定總目標前進一步 do 求出可行解的一個解元素； 由所有解元素組合成問題的一個可行解
貪心演算法最經典的例子，給錢問題。
比如中國的貨幣，只看元，有1元2元5元10元20、50、100 如果我要16元，可以拿16個1元，8個2元，但是怎麼最少呢？ 如果用貪心算，就是我每一次拿那張可能拿的最大的。比如16，我第一次拿20拿不起，拿10元，OK，剩下6元，再拿個5元，剩下1元 也就是3張 10、5、1。
每次拿能拿的最大的，就是貪心。但請注意，貪心得到的並不是最優解，也就是說用貪心不一定是拿的最少的張數，貪心只能得到一個比較好的解。
再思考一個問題，為什麼剛才的題目可以使用貪心演算法呢？因為我們國家的錢的大小設計，正好可以使得貪心演算法算出來的是最優解（一般國家的錢幣都會這麼設計）。
如果設計成別的樣子情況就不同了：
比如某國的錢幣分為 1元3元4元 ，如果要拿6元錢 怎麼拿？如果使用貪心演算法的話，先拿4，再拿兩個1， 一共3張錢 但實際最優呢？ 兩張3元就夠了
求最優解的問題，從根本上說是一種對解空間的遍歷。最直接的暴力分析容易得到，最優解的解空間通常都是以指數階增長，因此暴力窮舉都是不可行的。
最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解
。
貪心和動態規劃本質上是對子問題樹的一種修剪，兩種演算法都要求“子問題最優性”。即組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的。如果以自頂向下的方向看問題樹（原問題作根），那麼
每次只需要向下遍歷代表最優解的子樹就可以保證會得到整體的最優解
。
更具體地說，可以簡單的用一個值（最優值）代表整個子樹，而不用去求出這個子樹所可能代表的所有值，這就是動態規劃方法的解法思路。我們自底向上（從葉子向根）構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值捨棄。動態規劃的代價取決於可選擇的數目（樹的叉數）和子問題的的深度（樹的高度）。
貪心演算法是動態規劃方法的一個特例
。
貪心演算法的特殊之處在於，每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況
。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。通常這個值都是對於當前的問題情況下，顯而易見的“最優”值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，只需要自根開始，選擇最優的路，一直走到底就可以了。與動態規劃相比，它的代價只取決於子問題的深度，而選擇數目總為1。
找錢問題，可以很大程度上幫助我們理解動態規劃法語貪心演算法的區別
問題
現只有面額為11元、5元、1元的三種人民幣。 給定一個 數目為money 的人民幣，如何用這三種面額的人民幣找開它，且用的人民幣張數最少。 如：給定 10元，我們可以有以下找法： 2張 5元面額 1張 5元面額 + 5 張 1元面額 10張 1元面額
很明顯第一種找法只用2張5元面額的人民幣符合題目要求。
分析
利用動態規劃法可以找到最優解，而利用貪心演算法在題目的設定情況下，只能找到近似最優解。
如果現在要找開15元錢，那麼：
1。 根據動態規劃法的解題思想，得到最優解為3張 5元面額，總共 3張；
2。 根據貪心演算法的解題思想，得到的近似最優解為1張11元面額，加上4張1元面額，總共 5張
從這也可以大致看出兩者的區別
程式碼實現（動態規劃法與貪心演算法對比）
#include#define N 4 #define VALUE1 11 //面額為 11元的人民幣 （可以修改）#define VALUE2 5 //面額為 5元的人民幣 （可以修改）#define VALUE3 1 //面額為 1元的人民幣 （不要修改，不然會有找不開的情況）#define MAX_MONEY 1000 //能找開的錢的上限/***************************動態規劃法******************************** *方法： * int Num［MAX_MONEY］； //Num［i］儲存要找開 i 元錢，需要的最小人民幣張數 * int Num_Value［N］［MAX_MONEY］； //Num_Value［i］［j］ 表示 要找 j元錢，需要面額 VALUEi 的人民幣張數 * * Num［i］ = i； 0<= i <=4 * Num［i］ = min（Num［i-VALUE1］+1，Num［i-VALUE2］+1，Num［i-VALUE3］+1） *///————————————-求最小值————————————————-int min（int a，int b，int c）{ return a= 0）{ //如果比 11 元大，說明多了一種用11元面額人民幣的可能 //從用 11元、5元、1元中 選擇一個張數小的 Num［i］ = min（Num［i-VALUE1］+1，Num［i-VALUE2］+1，Num［i-VALUE3］+1）； } else{ //從5元、1元中 選擇一個張數小的 Num［i］ = （Num［i-VALUE2］+1） < （Num［i-VALUE3］+1） ？ （Num［i-VALUE2］+1）：（Num［i-VALUE3］+1）；// Num［i］ = min（Num［i-VALUE2］+2，Num［i-VALUE2］+1，Num［i-VALUE3］+1）； } } return Num［money］；}//————————————-求最優解————————————————-void BestChoice（int money，int Num［］，int Num_Value［N］［MAX_MONEY］）{ //要找 money 元錢，總人民幣張數放在Num［money］中 //Num［1~3］［money］分別儲存三種面額的張數 int i； for（i=0；i=VALUE1） && （Num［i］ == （Num［i-VALUE1］+1）））{ //i 是由 i-11+11 構成 即i元是由 i-11元 加上一張面額11元的人民幣構成 Num_Value［1］［i］ = Num_Value［1］［i-VALUE1］+1； //多一張 11元面額人民幣 Num_Value［2］［i］ = Num_Value［2］［i-VALUE1］； // 5元面額人民幣 張數一樣多 Num_Value［3］［i］ = Num_Value［3］［i-VALUE1］； // 1元面額人民幣 張數一樣多 } else if（Num［i］ == （Num［i-VALUE2］+1））{ //i 是由 i-5+5 構成 Num_Value［1］［i］ = Num_Value［1］［i-VALUE2］； //11元面額人民幣 張數一樣多 Num_Value［2］［i］ = Num_Value［2］［i-VALUE2］+1； //多一張 5元面額人民幣 Num_Value［3］［i］ = Num_Value［3］［i-VALUE2］； // 1元面額人民幣 張數一樣多 } else if（Num［i］ == （Num［i-VALUE3］+1））{ //i 是由 i-1+1 構成 Num_Value［1］［i］ = Num_Value［1］［i-VALUE3］； //11元面額人民幣 張數一樣多 Num_Value［2］［i］ = Num_Value［2］［i-VALUE3］； // 5元面額人民幣 張數一樣多 Num_Value［3］［i］ = Num_Value［3］［i-VALUE3］+1； //多一張 1元面額人民幣 } else{ } }}/***************************貪心演算法******************************** *方法： * Num_Value［i］表示 面額為VALUEi 的人民幣用的張數 * 能用大面額的人民幣，就儘量用大面額 */int Greed（int money，int Num_Value［］）{ //要找開 money元人民幣，Num_Value［1~3］儲存 三種面額人民幣的張數 int total=0； //總張數，返回值也即是總張數。 Num_Value［1］ = 0； Num_Value［2］ = 0； Num_Value［3］ = 0； for（int i=money；i>=1；）{ if（i >= VALUE1）{ Num_Value［1］++； i -= VALUE1； total++； } else if（i >= VALUE2）{ Num_Value［2］++； i -= VALUE2； total++； } else if（i >= VALUE3）{ Num_Value［3］++； i -= VALUE3； total++； } else{ } } return total；}void main（）{ //測試 動態規劃法/* int i； int money = 23； int Num［MAX_MONEY］； //Num［i］儲存要找開 i 元錢，需要的最小人民幣張數 int Num_Value［N］［MAX_MONEY］； //Num_Value［i］［j］ 表示 要找 j元錢，需要面額 VALUEi 的人民幣張數 printf（“%d/n”，DP_Money（money，Num））； printf（“——————————————————————-/n”）； BestChoice（money，Num，Num_Value）； printf（“——————————————————————-/n”）； for（i=0；i<=money；i++）{ printf（“Num［%d］=%4d， %3d， %3d， %3d/n”，i，Num［i］，Num_Value［1］［i］，Num_Value［2］［i］，Num_Value［3］［i］）； }*/ //測試 貪心演算法/* int i； int Num_Value_Greed［4］； for（i=0；i<=40；i++）{ //從0 元到 40 元的每一個找錢方式 Greed（i，Num_Value_Greed）； printf（“%d——>>> %d，%d，%d/n”，i，Num_Value_Greed［1］，Num_Value_Greed［2］，Num_Value_Greed［3］）； }*/ //比較兩個演算法 int i； int dp，grd； //分別儲存動態規劃法和貪心演算法得到的人民幣總張數 int money； //要找的錢 int Num［MAX_MONEY］； //Num［i］儲存要找i花費的銀幣的數目 int Num_Value［N］［MAX_MONEY］； //Num_Value［i］［j］ 表示 要找 j 花費的 面值為 VALUEi 的硬幣 的數目 int Num_Value_Greed［N］； //Num_Value_Greed［i］ 表示 面值為VALUEi 的人民幣 數目 money = 15； //可以為任意非負整型值（15 元是一個比較典型的可以區分兩種演算法的值） dp = DP_Money（money，Num）； //動態規劃法 BestChoice（money，Num，Num_Value）； grd = Greed（money，Num_Value_Greed）； //貪心演算法 printf（“要找的錢 為：%d/n/n”，money）； printf（“ 演算法 張數 11元 5元 1元/n”）； printf（“動態規劃 %-4d %-4d %-3d %-3d/n”，dp，Num_Value［1］［money］，Num_Value［2］［money］，Num_Value［3］［money］）； printf（“貪心演算法 %-4d %-4d %-3d %-3d/n”，grd，Num_Value_Greed［1］，Num_Value_Greed［2］，Num_Value_Greed［3］）；}
