***1、什么是贪心算法 *** 贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。 贪心算法总是做出在当前看来最好的选择。也就是贪心算法并不从整体最优上加以考虑，它所做出的选择只是某种意义上的局部最优选择。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。 **2、贪心算法的基本要素** （1）贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择达到。它也是贪心算法与动态规划算法的主要区别。 （2）最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。 **动态规划算法和贪心算法有一个显著区别：** 1）在动态规划算法中，以自底向上的方式来利用最优子结构，也就是说，首先找到子问题的最优解，解决子问题，然后找到问题的一个最优解。 2）在贪心算法中，以自顶向下的方式使用最优子结构，也就是说，贪心算法会先做出选择，在当时看起来是最优的选择，然后再求解一个结果子问题，而不是先求解子问题的最优解，然后再做出选择。 **两者的不同点：** 1 贪心算法作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。 2 动态规划算法的全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有局部最优解；