这两天做贪心的练习的时候，总是纠结于贪心策略是否正确，显然对于某些问题，如果没有「贪心算法」的标签，我还真不一定能看出来这是贪心的题。加之对动态规划的理解也不是很深刻，所以花了点时间理解了以下贪心和DP的区别。这里引用一段话

走出迷宫的人们，有的是认识路；有的是莽撞碰巧出来的；有的则是一路做着标记出来的；也有的是走遍了整个迷宫。 
——证明了的贪心算法、没有证明的贪心算法、动态规划、暴力搜索的区别。

从做题的经历来看，我经常会把贪心的题当成DP来做。事实上，的确所有的贪心问题都可以用DP做出来，反之则不一定成立。

既，DP和贪心都是搜索，但是与暴搜比起来，他们的优点就是进行了剪枝，从而避免了许多无用的搜索。直白一点的解释就是，DP和贪心不用遍历整个解空间，或者说不用重复计算某个子问题。

本质上来说，这两种算法具有最优子结构性质，既均用局部最优解来推导全局最优解 ，一般用递归实现。求全局最优解的问题，从根本上说是一种对解空间的遍历。而直接的暴力穷举很容易造成超时，在大多数情况下是不可行的。
但是最优解问题在大部分情况下都可以拆分成一个个的子问题，把解空间的遍历也可以视作对子问题树的遍历，则以某种形式对树遍历一遍就可以求出最优解。
贪心和动态规划本质上其实是对子问题树的一种修剪。两种算法要求问题都具有的一个性质就是「子问题最优性」，也称为「最优子结构」。即，组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的。如果以自顶向下的方向看问题树，则，我们每次只需要向下遍历代表最优解的子树就可以保证会得到整体的最优解。形象一点说，可以简单的用一个值（最优值）代表整个子树，而不用去求出这个子树所可能代表的所有值。

对于上图的数塔，从顶部出发在每一个节点可以选择向左或者向右走，一直走到底层，要求找出一条路径，使得路径上的数字之和最大。

从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只有左右两道路径上的最大值求出来了才能作出决策。同样的道理，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。 

上面的数塔问题就是对最优子结构很好的一个解释。

如对于上图红框内的子树，因为2+19>2+7，因此可以用21代替这一颗子树，对于其他子树也同理。而当我们处理完第五层的节点之后，剩下的问题就转化为四阶数塔，此时只要递归求解就可以了。

从这样一个经典动动规问题可以看出DP的本质，既：

1. 最优子结构：即每个大的数塔必定包含很多小的数塔，要求解大数塔的最大值，肯定要选择小数塔中和最大的路径。
2. 无后效性：这是判断一个问题能不能用dp做的重要标志之一；即某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。在数塔问题中，每次选择相加之和最大的节点，至于这个节点的和是怎么来的我不用管，也就是说“未来与过去无关”；但是如果说下一步的决策是受之前影响的（比如之前走过的点下一次就不能走了），那就叫有后效性，也就是：“未来受过去影响“。

---

至于二者的区别，其实也比较明显：贪心算法仅在当前状态下做出最好选择，即局部最优选择，然后再去解做出这个选择后产生的相应的子问题，而对于这个问题，全局最优解可以通过局部最优得到，可以采用贪心算法；

相应的，DP算法每步所做的选择往往依赖于相关子问题的解，因而只有在解出相关子问题时才能做出选择。动规就是将一个大问题分解为若干的小问题，然后再对小问题求解的过程。一个最简单的例子就是用尾递归实现斐波那契数列的算法。 

深入一点地讲，我以为二者最本质的区别是：DP的选择策略是试探性的，每一步要试探所有的可行解并将结果保存起来，最后通过回溯的方法确定最优解，这也就是为什么DP解题一般采用自底向上的解法，形象地说，DP问题对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃（参考数塔问题）。而贪心算法每一次的都是对于局部最优进行选择，通过对候选解空间按照一定的规则进行排序，然后就可以按照这个排好的顺序进行选择了，选择过程中仅需确定当前元素是否要选取，与后面的元素是什么没有关系。形象地说，对于能够贪心的题，每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。通常这个值都是对于当前的问题情况下，显而易见的“最优”情况。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。

---

经过一顿分析，不难看出，能用贪心做的题都可以用DP做，反之则不一定。

因此，我们可以知道：满足贪心选择性质的问题可用贪心算法解决，不满足贪心选择性质的问题只能用动态规划解决。可见能用贪心算法解决的问题理论上都可以利用动态规划解决，而一旦证明贪心选择性质，用贪心算法解决问题往往比动态规划具有更低的时间复杂度和空间复杂度。为什么说是「往往」呢，我们后面再说。

这里又提到了一个概念叫「贪心选择性质」，这个是什么呢，让我们举个例子：

找钱问题：

现有1，5，10，20，50，100面额的钱币，且每种面额的钱币的数量都足够多，那么如果让找出12块钱，绝大多数人会用一张10元的两张1元的来凑足12元。或许你没有察觉到，其实在这个过程中我们已经用到了贪心算法，不相信？那假如要找277元，该用几张1元的？我相信没人可以直接回答找277要用几张1元的，我们的思维方式都是想先用两张100的，剩77再用一张50的，最后确定用几张1元的。这就说明了贪心选择前的排序过程（既之前说的对候选解空间按照一定的规则进行排序），也就是说我们的贪心选择必须从大面值的开始，而不能从小面额的开始。每次拿能拿的最大的，这就是贪心。

那么假如是我们的钱币面额是1，2，7，10，那我们要找14元，还可以用贪心选择策略来选择吗？显然就不能了，两个7元才是张数最少的解。那问题来了，为什么1，5，10，20就可以1，2，7，10就不行呢？这就涉及到我们所说的「贪心选择性质」了。

1，5，10，20满足贪心选择性质，而1，2，7，10就不满足。

要证明一个问题的贪心选择性质的正确性，既证明贪心选择是安全的是一件很难的事情（从数学上来说），但是我们经常可以通过举反例来推翻其正确性（如1，2，7，10面额的货币问题），事实上在大多数情况下我们也是这么做的。

对于贪心策略的证明理解起来难度不小，《算法导论》上对于贪心算法章节的描述也十分抽象，下面让我们引入一个引例：部分背包问题。

• 问题描述
  有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
  
• 问题分析
  1.目标函数： ∑pi最大，使得装入背包中的所有物品pi的价值加起来最大。
  2.约束条件：装入的物品总重量不超过背包容量：∑wi<=M( M=150)
  3.贪心策略：
  • 选择价值最大的物品
  • 选择价值最大的物品
  • 选择单位重量价值最大的物品
    有三个物品A,B,C，其重量分别为{30,10,20}，价值分别为{60,30,80}，背包的容量为50，分别应用三种贪心策略装入背包的物品和获得的价值如下图所示：

显然，由于物品可分割，我们显然可以得出这样的结论：每次只需装入性价比最高的物品。为什么可以这样做呢？

我们将物品按照单位价值V_i/W_i从大到小排好序的，即：V₁/W₁ >  V₂/W₂  >  …  >  V_n/W_n。

于是部分背包问题的贪心选择性质可以描述为：每次从C_i,j中选择物品，都是优先考虑选择物品i，且在满足条件1的情况下，X_i 越接近1越好。下面用数学归纳法证明这一贪心选择性质：

记A_i,j为从物品C_i,j中选择装进背包的最优解，则原问题为求A_1,n。再记k为第k次从C中选物品进背包。则：

Ⅰ）当k=1时，满足贪心选择性质，即第一次选物品p进背包，且p=1。下面用反证法证明：

若p≠1，则p≥2。但在此情况下不能保证A_1,n最优。试考虑W₁=W的情况下，另外一个解A_1,n^’={1}的价值V^’更大（因为V₁/W₁ > V₂/W₂ > …> V_n/W_n）。既A_1,n不是最优解，产生矛盾。所以p=1。

Ⅱ）在满足条件1的情况下，假设k≤z时，满足贪心选择性质。既前z（包括z）次从C_z,n中选择物品，都是优先考虑选择物品z，且在满足条件1的情况下，X_i 越接近1越好。

Ⅲ）在满足条件1的情况下，当k=z+1时，证明也满足贪心选择性质，既第k=z+1次选物品（z+1）。

先证明A_1,n的子问题A_z+1,n也具有最优性质：如果存在C_z+1,n中选择物品的子问题的解A_z+1,n^’的总价值比A_z+1,n的总价值更大，那么A_z+1,n^’与A_1,z合并后的原问题的解A_1,n^’的总价值比A_1,n的总价值更大。这与A_1,n是最优解矛盾。所以A_z+1,n也具有最优性质。

于是第k=z+1次选择物品等价于子问题A_z+1,n的第一次选择物品，又因为在Ⅱ）假设成立的情况下，C_1,n的前z个物品已经被选了，所以转换成A_z+1,n从C_z+1,n中选择第一个物品。根据Ⅰ），显然优先选择物品（z+1）。所以结论得证。

∴ 综合Ⅰ）Ⅱ）Ⅲ），得证部分背包问题具有最优选择性质。

以上，通过数学归纳法证明了部分背包问题的贪心选择正确性。那么推而广之，我们对于贪心问题正确性的证明步骤如下（的确有些抽象）

考察一个问题的最优解,证明可修改该最优解,使得其从贪心选择开始,然后用数学归纳法证明每一步都可以通过贪心选择得到最优解：
1,假定首选元素不是贪心选择所要的元素,证明将首元素替换成贪心选择所需元素,依然得到最优解；
2,数学归纳法证明每一步均可通过贪心选择得到最优解。

因此我们可以说，贪心选择性质即存在一个最优解是以贪心选择开始的。 也即：如果假设的全局最优解是第一个贪心选择，即成立；如果不是，则剪枝，然后将通过贪心选择的第一个粘贴上去，也就证明了无论什么情况都是从贪心选择开始的。

---

通过以上的分析，我们不难看出，贪心算法其实是动态规划方法的一个特例。贪心特在，我做一个决定的时候，不需要考虑这个决策对之后选择的影响，只需考虑当前最优，下一步的最优解由上一步的最优解推导得到；

比如对于0-1背包问题，既每个物品只能选择选或不选，贪心策略是有问题的。

为什么物体可以分割时能用贪心算法，而物体不能分割时就不行呢？这里想让大家注意一下「回退」的概念，这个需要「回退」的概念就是贪心选择性质失败的标志。

在背包问题中，如果物体可以分割，那我们装入单位质量最贵的东西“显然”是正确的，而如果物品不可分割，那就可能出现背包装了一个单价很贵的东西但没有装满，而后面一个虽然单价比较低但体积也比较大，这样就装不进去了，如果把前面那个东西倒出来把这个大的装进去可能就会使得总价值更大。总之这个问题在于背包可能装不满，而如果有一个物体单价低但占的空间更充分的话就有可能会得到更好的解。所以这个问题就需要往回试探的过程，这个就是要使用动态规划的标识。动态规划的选择策略就是试探性的，最后通过回溯的方法确定最优解，这是贪心算法不具备的。

再想一想找钱问题，因为两个7等于14，而选择10的时候我们并不知道后面有没有4可以选择，如果后面发现没有4再回头把10拿出来就会使整个搜索过程陷入混乱，贪心算法不允许“往回拿”的操作，通俗点讲，贪心就是“一锤子买卖”，这也正是贪心策略失效的原因。

---

但是我们必须要意识到，贪心算法是优化了选择的策略，而非与动态规划背道而驰，贪心算法仅仅是动态规划的一个平凡态罢了。一般情况下，我们认为贪心是对动规的一种优化，因此，对于一个给定问题，先对问题的解空间建模，如果得到最优子结构的性质，写出状态转移方程，再看某些维度是否有贪心的优化余地。

如果问题可以选择贪心做法，一般情况下我们会选择贪心，但是话说回来，既然是研究一个算法，必然要分析一下其时间复杂度与空间复杂度。那么，是不是对于所有具有最优子结构的问题，在能选择贪心优化时都要选择贪心呢？未必哦。贪心算法确实可能比其对应的动态规划快不少，因为它的常数可能小得多。并且在思维难度上，贪心比动规简单了不少 。

为了直观一点地验证这一结论，下面贴上0-1背包和部分背包的代码。

int main(){
    
    int w[maxn],v[maxn];//w为质量，v为价值，r为价值与质量的比
    float r[maxn];//r为价值与质量的比
    int n;//物品的数量
    int m; //背包的容量
    scanf("%d %d",&m,&n);   //输入背包总量和数量
    for(int i=0;i<n;i++){
        scanf("%d %d",&w[i],&v[i]);
    }
    for(int i=0; i<n; i++){
        r[i]=v[i]*1.0/w[i];
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<n-i;j++){
            if(r[j]<r[j+1]){
                int x;
                double y;
                y=r[j];r[j]=r[j+1];r[j+1]=y;
                x=w[j];w[j]=w[j+1];w[j+1]=x;
                x=v[j];v[j]=v[j+1];v[j+1]=x;
            }
        }
    }
    int i=0;
    while(m){
        if(w[i]<=m){
            m-=w[i];
            printf("价值：%d取：%d\n",v[i],w[i]);
            i++;
        }
        else{
            printf("价值：%d取：%d\n",v[i],m);
            m=0;
        }
    }
    return 0;
}

0-1背包

int T,n,bag;
    int dp[maxn],v[maxn],w[maxn];
    while(cin>>T)
    {
        while(T--)
        {
            memset(v,0,sizeof(v));
            memset(w,0,sizeof(w));
            memset(dp,0,sizeof(dp));
            cin>>n>>bag;
            for(int i=0;i<n;i++) cin>>v[i];
            for(int i=0;i<n;i++) cin>>w[i];
            for(int i=0;i<n;i++)
                for(int j=bag;j>=w[i];j—)//完全背包则正序循环  
                {
                    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
                }
            cout<<dp[bag]<<endl;
        }
    }

从以上的对比可以看出：DP的代码十分简洁，但是理解起来的难度不小，不像贪心那样通俗易懂。

一般地，在算法竞赛中，我们采用如下的优化策略：

优化与否取决于动态规划中计算所有可选的策略的代价，如果代价是常数的，那么将其贪心优化并不会带来时间复杂度的下降，该走的解空间还是要走，只是不保存其中的一些值而已，可能会带来空间复杂度的下降。

以上已经是进阶操作了（稍微有点超纲），需要有比较扎实的算法基础和相当大的刷题量，还需要读者慢慢体会。