一.贪心算法
贪心算法是在每个局部阶段，都做出一个看上去最优的决策（即某种意义下的、或某个标准下的局部最优解），并期望通过每次所做的局部最优解选择产生出一个全局最优解。
若硬币的面值改为一分、五分和一角一分3种，而要找给顾客的是一角五分钱。还用贪心算法，将找个顾客1个一角一分的硬币和4个一分的硬币。然而，3个五分的硬币显然才是最好的找法。
顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在许多情况下，应用贪心算法能够得到整体最优解；在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
一般地，有这样一类问题：它有n个输入，而它的解就由这n个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。把那些必须满足的条件称为约束条件；而把满足约束条件的子集称为该问题的可行解。为了衡量可行解的优劣，事先给出了一定的标准。一般以函数形式给出，称为目标函数。那些使目标函数取极值（极大或极小）的可行解，称为最优解。
可以用贪心算法求解的问题一般具有2个重要的性质：最优子结构性质和贪心选择性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。那么如何去理解这个最优子结构呢，笔者尽量用简单易懂的语言来进行讲述。
比如我们所求解的分数背包问题，可以化解为Si=Sk+ak，ak是Si里面平均价值最高的，Sk是选择ak剩下来的物品。 而在我们的活动分配问题中，也可以化解为Si=Sk+ak，ak是Si里面活动结束时间最早的一个，Sk是选择ak之后剩下的最优活动。在jump game问题中，也可以化解为Si=Sk+ak，ak是Si里面到达某一个点后能跳的最远距离，Sk是除掉这个点之后的最远距离。
贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。贪心选择每次选取当前最优解，因此它依赖以往的选择，而不依赖于将来的选择。贪心算法通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
大家在生活中都有找零钱的经历，假如每种面额的钱币的数量都足够多，那么如果让找出14块钱，那绝大多数人会用一种10元的两张2元（假设还有2元的纸币）的来凑足14元。或许你没有察觉到，其实在这个过程中我们已经用到了算法，即贪心算法。正如前文提到的，贪心算法就是根据人思维模式设计的算法，所以平常生活中有很多这样的例子。
先来说说找钱的具体过程。仔细琢磨一下我们的选择过程：因为14>10，所以选择一张10元的，还剩4元，正好用两个2元的凑足。这个例子比较小，可能还不够说明问题，我们这样来想，假入要找177元，该用几张1元的？快点儿，仔细想一下，到底用几张？怎么样，发现问题了吧。没人可以直接回答找177要用几张1元的，我们都是想先用一张100的，剩77再用一张50的……最后确定用几张1元的。这个过程大家已经经历了无数次了，所以已经形成条件发射了。但仔细想想，这就说明了贪心选择前的排序过程，也就是说我们的贪心选择必须从大面值的开始，而不能从小面额的开始。
再来看看我们这样做的依据。为什么我们要这么选择钱的种类呢？为什么我们可以这样选择呢？首先要明确我们的目标，为什么我们不用7张2元的来凑14元，显然我们的目的是使钱的总张数最少。那我们这样选择一定可以保证无论找多少零钱，总的张数都是最少的吗？答案仿佛是不言自明的，但这里面仍有一些细节需要了解。假如我们的纸币系统的面额不是1、2、5、10这样的数，假如是我们的是1、2、7、10，那我们要找14元，还可以用贪心选择策略来选择吗？显然就不能了，两个7元的显然是最优解，即用的张数最少的解。那问题来了，为什么1、2、5、10就可以1、2、7、10就不行呢？不行了该怎么办呢？
找钱问题的贪心选择性质。前面已经提到，找钱问题实质是贪心选择性质的应用，而现在1、2、7、10用不了了，那就说明贪心选择性质失效了。失效了就不能用贪心选择了，只能用动态规划了！先来看一下为什么会失效，也就是说，什么样的数字组合才满足贪心选择性质呢？非常抱歉，这个问题本人还没有找到答案。但我们可以肯定的是某些组合时不具有贪心选择性质的，对于这样的组合我们举个反例就可以了，就像上面的两个7可以凑足14一样。
二.动态规划算法
动态规划解找零钱问题。好了，我们回到正题。我们已经分析了钱的面额合适的时候可以用贪心选择，而这个策略并不具有通用性，钱币面额稍作改变就不满足贪心策略了，我们的方法就不能用了。那下面我们来研究一下通用的算法，即用动态规划来找零钱。
我们设钱币的种类数为N，并且假设每种钱币的数量都足够多。
钱币的面额为ai（0≤i≤N-1），且ai为正整数，即假设不需要找1元以下的钱。同时我们假设a0=1，否则会有找不开的情况。
要找的零钱数为j（0≤j≤J），同上，j也是正整数。
我们确定决策过程T(i,j)为用前i种钱币找出j元所用的最少张数。则有，T(i,0)=0（其中，0≤i≤N-1），即如果要找的零钱为0，那肯定一张也不用。T(0,j)=j（其中，0≤j≤J），即只用1元的纸币，那找多少钱就用多少张。
T(i,j)=min{T(i-1,j),T(i,j-ai)+1}（其中，j≥ai），即当我们的钱币种类增加到第i种时，这个第i种是可以用上的，如果用了就是T(i,j-ai)+1，如果没有用就是T(i-1,j)。还有一种情况是这个钱不能用，也就是j＜ai，这个钱的面额超过了我们要找的钱，自然就用不上了，此时T(i,j)=T(i-1,j)。
三、区别
所以在我看来两者的区别就在于贪心算法是每次只求出一个最优解，这个最优的依据是我们自己定义的策略。而动态规划是每次求很多个解，然后取其中最优的那个。所以说，用贪心算法能解的问题，动态规划都能解；贪心算法是动态规划的一个特例；一般来说贪心算法比动态规划复杂度要低。而且，贪心算法是自顶向下找最优解，动态规划是自低向上找最优解。