动态规划和贪心算法都是一种递推算法，均用局部最优解来推导全局最优解，对于很多学习算法的同学来说很是迷惑。那么它们之间的区别究竟是什么呢？且听我慢慢道来 贪心算法与动态规划区别

贪心算法：

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<stdio.h>#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<b ? (a<c ? a:c):(b<c ? b:c);}//-------------------------求最优值---------------------------------int DP_Money(int money,int Num[]){ //获得要找开money元钱，需要的人民币总张数  int i; for(i=0;i<=VALUE2;i++){ //0~4 全用 1元  Num[i]=i; } for(i=VALUE2;i<=money;i++){ //从5元开始 凑钱 if(i-VALUE1 >= 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<VALUE2;i++){  Num_Value[1][i] = 0; Num_Value[2][i] = 0; Num_Value[3][i] = i; } for(i=VALUE2;i<=money;i++){ if((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]);}