在前言中，我讲了动态规划。看资料的时候看到很多在讲贪心算法。这两个算法也非常相似。刚好我最近解决了关于贪婪的问题。所以今天写一篇文章来谈谈。贪心算法（英语：greedyalgorithm），又称贪心算法，是在每一步选择中，取当前状态下最好或最优（即最有利）的选择，希望导致最好或最有利的结果。优秀的算法。贪心算法在具有最优子结构的问题中特别有效。最优子结构是指局部最优解可以决定全局最优解。简单的说就是可以将问题分解成子问题来求解，子问题的最优解可以推导出最终问题的最优解。贪心算法和动态规划的区别在于它对每个子问题的解都做出选择，不能倒退。动态规划会保存之前的计算结果，并根据之前的结果选择当前的，具有回滚功能。贪心法可以解决一些优化问题，比如：求图中的最小生成树，求哈夫曼编码……对于其他问题，贪心法一般得不到我们需要的答案。一旦一个问题可以用贪心法解决，那么一般来说贪心法就是解决问题的最好方法。由于贪心法效率高，得到的答案比较接近最优结果，所以贪心法也可以作为一种辅助算法，或者直接解决一些对结果要求不准确的问题。——摘自维基百科动态规划与贪心算法非常相似。在对它们的各种描述中，有把问题分解成子问题的说法。其实也有分而治之的方法。但是动态规划本质上是一种穷举法，只是省去了重复的计算，而贪心算法就像它的名字一样，贪心，每次都选择局部最优解，而没有考虑这个局部最优选择对整体的影响。可以说贪心算法是动态规划的特例，并且由于贪心算法只考虑子问题的最优解，可以说贪心算法实际能解决的问题是有限的。是一种只考虑当下的短视算法，只有当这样一种基于局部最优的选择最终能够导致整体最优解时，才可以采用贪心算法来求解。举个栗子，看一下leetcode上的一个问题：假设你是一位伟大的父母，想给你的孩子一些饼干。但是，每个孩子最多只能得到一个饼干。对于每个孩子i，都有一个食欲值gi，这是满足孩子食欲的最小尺寸的饼干；每个饼干j的大小为sj。如果sj>=gi，我们可以将这个cookiej分配给孩子i并且这个孩子会满意。你的目标是让尽可能多的孩子满意，输出这个最大值。注意：您可以假设胃口值为正。一个孩子最多只能吃一块饼干。来源：LeetCode链接：https://leetcode-cn.com/probl...版权归LeetCode网络所有。商业转载请联系官方授权，非商业转载请注明出处。是的，这是一个伟大的（吝啬的）父母，试图用尽可能少的饼干来满足尽可能多的孩子。比如有3个孩子，胃口是[1,2,3]，那么即使父母有一百块大小为1的小饼干，也只能满足一个孩子，因为他最多只能给每个孩子一块饼干。我们想想如何“贪心”？为了最省饼干，我们可以先把饼干大小和孩子胃口这两个数据从小到大排序，然后每次都用最小的饼干，尽量满足胃口最小的孩子，所以需要维护两个索引。代码实现：classSolution:deffindContentChildren(self,g:List[int],s:List[int])->int:count=0g.sort()s.sort()gi,si=0,0whilegi
