在前面的章节中，我们学了递归、二分查找、排序、哈希表、图的遍历、二叉树和动态规划。今天我们来认识一个思路非常「朴素」但威力巨大的算法思想——贪心算法（Greedy Algorithm）。贪心算法的核心理念就一句话：每一步都选当前看起来最好的选择，期望最终得到全局最优解。听起来是不是很简单？但正是这种「目光短浅」的策略，在很多场景下却能给出正确的答案。1. 什么是贪心算法1.1 一句话解释贪心算法在每一步决策时，都选择当前状态下最优的那个选项，不考虑这个选择对未来的影响，也不会回头修改之前的选择。你可以把它想象成走迷宫：每到一个岔路口，你都选「看起来离出口最近」的那条路，不走回头路。1.2 贪心 vs 动态规划贪心和动态规划（DP）都是用来求最优解的，但思路完全不同：维度贪心算法动态规划决策方式每步只看当前最优考虑所有子问题的最优组合是否回溯不回溯通过状态转移回顾子问题正确性只对特定问题有效对具有最优子结构的问题都有效效率通常更快通常更慢但更通用简单来说：贪心是 DP 的特例。能用贪心解决的问题，一定也能用 DP 解决，但反过来不行。2. 贪心适用的条件一个问题能用贪心算法求解，需要满足两个条件：2.1 贪心选择性质通过局部最优选择能够达到全局最优。也就是说，「当前最好的选择」不会让你掉进坑里。2.2 最优子结构问题的最优解包含其子问题的最优解。这一点和 DP 的要求一样。关键在于：不是所有问题都满足贪心选择性质。如果一个问题不满足，用贪心得到的可能只是一个「还不错」的解，而不是「最好的」解。3. 经典例子 1：找零钱问题你是一个收银员，需要用最少的硬币数找零。现有硬币面值为 1 元、5 元、10 元、25 元。顾客需要找零 41 元，最少需要几枚硬币？3.1 贪心思路每次选面值最大的硬币，尽量多用：41 ÷ 25 = 1 枚 25 元，剩余 16 元16 ÷ 10 = 1 枚 10 元，剩余 6 元6 ÷ 5 = 1 枚 5 元，剩余 1 元1 ÷ 1 = 1 枚 1 元总共 4 枚硬币。对于这套面值（1、5、10、25），贪心策略恰好能得到最优解。3.2 代码实现#includeiostream#includevectorusingnamespacestd;intminCoins(vectorintcoins,intamount){// 从大到小排序sort(coins.begin(),coins.end(),greaterint());intcount=0;for(intcoin:coins){while(amount=coin){amount-=coin;count++;cout"使用 "coin" 元，剩余 "amount" 元"endl;}}returncount;}intmain(){vector