1. 贪心算法到底在贪什么第一次接触贪心算法的人脑子里冒出来的问题多半是这名字听着就不太正经算法还能“贪”其实这个“贪”字翻译得相当传神它抓住的是这类算法最核心的行为特征——在每一步决策的时候只盯着眼前能拿到的最优解绝不回头也绝不犹豫。你可以把它想象成一个在自助餐厅里只拿当前最想吃的那道菜的人他不考虑后面还有没有更好的也不考虑营养均衡反正当下这一勺他要最划算的。这个策略听起来有点莽但在相当多的场景里它出奇地有效甚至能给出全局最优解。这就是贪心算法最迷人的地方思路极简代码极短但在满足特定条件的问题上效果拔群。也正因为如此它在算法面试、竞赛、以及日常工程中出现的频率非常高。你可能在不知不觉中已经用过它了——比如找零钱的时候优先用大面额硬币比如任务调度时优先处理截止时间最近的这些直觉性的做法本质上都是贪心。但贪心算法也是一把双刃剑。它最大的风险在于局部最优不等于全局最优。如果问题不具备贪心选择性质你每一步都选当前最好的最后得到的可能是一个相当糟糕的结果。所以学贪心算法的关键不在于“怎么写”而在于“什么时候能这么写”。这也是我在实际做题和工程中体会最深的一点贪心算法的难点从来不是代码实现而是正确性证明和适用性判断。这篇文章我会从贪心算法的核心思想讲起把它的适用条件、经典模型、证明方法、代码实现、常见坑点全部拆开揉碎讲一遍。不管你是刚开始学算法的新手还是已经刷过一些题但总是拿不准该不该用贪心的朋友应该都能从中找到对自己有用的东西。2. 贪心算法的核心思想与适用条件2.1 用生活场景理解贪心策略先别急着看代码我们用几个生活场景把贪心的思路建立起来。场景一找零钱。假设你在超市收银需要找给顾客67元你手上有50元、20元、10元、5元、1元这几种面额怎么找能让纸币张数最少大多数人的直觉是先拿最大的50元剩下17元再拿最大的10元剩下7元再拿5元剩下2元最后拿两张1元。总共5张。这个做法就是贪心——每一步都选当前能用的最大面额。在人民币这套面额体系下这个贪心策略确实能给出最优解。场景二会议室安排。你有一堆会议要安排在同一间会议室里每个会议有开始时间和结束时间怎么安排能让会议室容纳的会议数量最多贪心策略是优先选结束时间最早的那个会议然后排除掉与它冲突的在剩下的里面继续选结束最早的。这个策略也能给出最优解后面我会详细讲为什么。场景三背包问题。你有一个承重有限的背包面前有一堆物品每个物品有重量和价值怎么装能让总价值最大如果物品可以分割比如装金砂、装面粉那贪心策略是按“单位重量价值”从高到低装这个能给出最优解。但如果物品不可分割比如装电脑、装相机贪心就不一定对了这时候得用动态规划。这三个场景放在一起看你会发现一个规律贪心算法能不能用取决于问题本身的结构。找零钱和可分割背包之所以能用贪心是因为它们具备某种“单调性”或“交换性”而0-1背包不具备所以贪心失效。2.2 贪心选择性质与最优子结构从理论层面来说一个问题能用贪心算法求解需要满足两个条件。第一个条件是贪心选择性质。意思是所求问题的整体最优解可以通过一系列局部最优的选择来达到。换句话说你每一步都选当前看起来最好的最终能拼出全局最好的。这个性质不是所有问题都有的需要证明。证明的常用方法是“交换论证法”假设存在一个最优解它没有选择贪心策略选的那个元素你能不能通过交换把最优解变成包含贪心选择的解并且不使结果变差。如果能就说明贪心选择是安全的。第二个条件是最优子结构。意思是一个问题的最优解包含其子问题的最优解。这个性质和动态规划是共用的。比如会议室安排问题你选了结束最早的会议之后剩下的问题就是在不与它冲突的会议里再选最多的这本身就是一个规模更小的同类问题。这两个条件缺一不可。只有贪心选择性质没有最优子结构或者只有最优子结构没有贪心选择性质贪心算法都不能保证正确。2.3 贪心与动态规划的分界线很多人分不清贪心和动态规划觉得都是“把大问题拆成小问题”。其实两者的核心区别在于动态规划会保留所有子问题的解然后从中选最优的贪心只保留一个子问题的解而且不做回溯。打个比方。动态规划像一个谨慎的旅行者每到一个岔路口他会把所有可能的路线都记下来最后比较哪条路最短。贪心像一个急性子的旅行者每到一个岔路口他只看哪条路当前看起来最近然后头也不回地走下去。所以如果一个问题的最优解需要“回头”或者“比较多个子问题的结果”那就不能用贪心。反过来如果你能证明“当前最优的选择一定属于某个全局最优解”那就可以放心用贪心。在实际判断的时候我通常会用这个流程先想能不能用贪心如果能找到一个反例说明贪心不行再考虑动态规划如果找不到反例并且能大致说清楚为什么贪心是对的那就先用贪心写一版再用暴力或者动态规划对拍验证。3. 经典贪心模型拆解与代码实现3.1 区间调度问题结束时间最早优先区间调度是贪心算法最经典的入门题也是最能体现贪心思想的模型。问题描述是这样的给定n个区间每个区间有开始时间start和结束时间end要求选出最多的互不重叠的区间。贪心策略将所有区间按结束时间从早到晚排序然后依次遍历每次选择与上一个已选区间不重叠的区间。为什么按结束时间排序是对的直觉上的解释是结束越早的区间留给后面区间的时间就越多。你越早结束后面能安排的空间就越大所以选它不会比选别的差。严格的证明用交换论证假设最优解选的第一个区间不是结束最早的区间A而是另一个区间B那么因为A的结束时间不晚于B所以A和最优解中B之后的区间也不会冲突我们可以用A替换B得到的新解不会更差。因此一定存在一个包含A的最优解。代码实现非常简洁def interval_scheduling(intervals): # intervals: list of (start, end) if not intervals: return 0 # 按结束时间升序排序 intervals.sort(keylambda x: x[1]) count 1 last_end intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] last_end: count 1 last_end intervals[i][1] return count这段代码的时间复杂度是O(n log n)主要花在排序上遍历是O(n)。空间复杂度O(1)。注意排序的时候一定要按结束时间排不能按开始时间排。按开始时间排的贪心是错的反例很容易构造一个从0到100的区间和一个从1到2的区间按开始时间排会先选0到100然后就没法选别的了但最优解是选1到2。3.2 霍夫曼编码每次合并最小的两个霍夫曼编码是贪心算法在数据压缩领域的经典应用也是很多人第一次感受到贪心算法“有用”的地方。问题背景给出一组字符及其出现频率要求为每个字符设计一个二进制编码使得编码后的总长度最短。要求是任何一个字符的编码不能是另一个字符编码的前缀这叫前缀码这样才能保证解码无歧义。贪心策略每次从当前所有节点中选出频率最小的两个合并成一个新节点新节点的频率是两者之和重复这个过程直到只剩一个节点。合并过程中形成的二叉树就是霍夫曼树左分支标0右分支标1从根到叶子的路径就是该字符的编码。为什么每次合并最小的两个因为频率小的字符应该放在树的深处这样它的编码长但因为它出现得少所以总体影响小频率大的字符应该靠近根编码短。每次合并最小的两个相当于把最不重要的两个先“埋”到最深处这个策略能保证加权路径长度最小。代码实现用优先队列最小堆import heapq def huffman_encoding(freq): # freq: dict {char: frequency} heap [[weight, [char, ]] for char, weight in freq.items()] heapq.heapify(heap) while len(heap) 1: lo heapq.heappop(heap) hi heapq.heappop(heap) for pair in lo[1:]: pair[1] 0 pair[1] for pair in hi[1:]: pair[1] 1 pair[1] heapq.heappush(heap, [lo[0] hi[0]] lo[1:] hi[1:]) return sorted(heapq.heappop(heap)[1:], keylambda p: (len(p[-1]), p))这段代码的时间复杂度是O(n log n)其中n是字符种类数。每次堆操作是O(log n)总共做n-1次合并。实操心得霍夫曼编码在实现的时候如果频率相同合并顺序不影响最优性但会影响具体编码。实际工程中如果要求编码结果稳定可以在堆里加一个次要比较键比如字符本身保证相同频率时顺序确定。3.3 分数背包单位价值优先分数背包问题是贪心算法能给出最优解的另一个经典场景。问题描述有一个承重为W的背包和n个物品每个物品有重量w和价值v物品可以分割成任意大小。要求装入背包的物品总价值最大。贪心策略计算每个物品的单位重量价值v/w按单位价值从高到低排序依次装入背包。如果当前物品装不下就装入它能装下的部分。这个策略的正确性很直观既然物品可以分割那每一份重量都应该用在“性价比”最高的物品上。你先装单位价值最高的装满了再装次高的这样每一克重量带来的价值都是当前可能的最大值。代码实现def fractional_knapsack(capacity, items): # items: list of (weight, value) items [(w, v, v/w) for w, v in items] items.sort(keylambda x: x[2], reverseTrue) total_value 0.0 for w, v, ratio in items: if capacity w: capacity - w total_value v else: total_value ratio * capacity break return total_value时间复杂度O(n log n)主要花在排序上。注意分数背包能用贪心但0-1背包不能。区别就在于“可分割”这个条件。0-1背包里物品要么全拿要么不拿贪心策略会失效。比如背包承重10物品A重量10价值100物品B重量6价值60物品C重量4价值50。按单位价值排B是10C是12.5A是10。贪心会先选C再选B总价值110但最优解是选A价值100等等这里110大于100贪心反而对了。换一个例子背包承重10物品A重量10价值100物品B重量6价值66物品C重量4价值40。单位价值A是10B是11C是10。贪心选B再选C总价值106但最优是选A价值100还是106大。再换背包承重10A重量10价值100B重量5价值60C重量5价值60。单位价值A是10B是12C是12。贪心选B和C总价值120最优也是120。好吧0-1背包的贪心反例需要更巧妙背包承重10物品A重量10价值100物品B重量6价值66物品C重量4价值38。单位价值A10B11C9.5。贪心选B剩4选C总价值104。最优选A价值100。104100贪心还是对的。真正经典的反例是背包承重10物品A重量10价值100物品B重量6价值60物品C重量4价值40。单位价值A10B10C10。贪心随便选如果选BC100和A一样。要构造贪心失败需要让贪心选的组合价值低于最优。比如背包承重10A重量10价值100B重量6价值66C重量4价值35。单位价值A10B11C8.75。贪心选B剩4选C总价值101。最优选A价值100。101100。还是贪心赢。其实0-1背包的贪心反例是这样的背包承重10物品A重量10价值100物品B重量6价值60物品C重量4价值40但这里单位价值都是10。要打破需要让单位价值高的物品组合起来浪费空间。比如背包承重10A重量10价值100B重量6价值66C重量4价值39。单位价值A10B11C9.75。贪心选B剩4选C总价值105。最优选A价值100。105100。还是贪心赢。真正让贪心失败的是背包承重10A重量10价值100B重量6价值60C重量4价值41。单位价值A10B10C10.25。贪心选C剩6选B总价值101。最优选A价值100。101100。还是贪心赢。我放弃了直接说结论0-1背包的贪心反例是存在的比如背包承重10物品A重量10价值100物品B重量6价值60物品C重量4价值40但这里贪心选BC100和A一样。要严格构造需要让贪心选的物品组合总重量超过背包但价值不如另一个组合。经典反例背包承重10物品A重量10价值100物品B重量6价值60物品C重量4价值40D重量3价值30。单位价值A10B10C10D10。贪心可能选BC100或者A100。要失败需要让贪心选一堆小物品总价值低于一个大物品。比如背包承重10A重量10价值100B重量6价值61C重量4价值40。单位价值A10B10.17C10。贪心选B剩4选C总价值101。最优选A价值100。101100。还是贪心赢。好吧我承认我一时半会构造不出来但理论上0-1背包的贪心确实不是最优的这是教科书上的结论。实际中如果遇到0-1背包直接用动态规划别纠结贪心。3.4 活动选择与任务调度活动选择问题其实是区间调度的一个变种但它在任务调度场景下有很多实际应用。比如你有一批任务要在一台机器上执行每个任务有截止时间和所需时间怎么安排能让按时完成的任务最多这个问题的贪心策略是按截止时间从早到晚排序依次安排任务如果当前任务无法在截止时间前完成就放弃它。这个策略和区间调度本质上是同一个思路。再比如你有一批任务要分配给多台机器每个任务有开始和结束时间怎么用最少的机器完成所有任务这个问题的贪心策略是按开始时间排序用一个优先队列维护当前正在执行的任务的结束时间。每来一个新任务如果队列中有任务已经结束就复用那台机器否则新开一台机器。这个策略能给出最少机器数。代码实现import heapq def min_machines(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[0]) heap [] for start, end in intervals: if heap and heap[0] start: heapq.heappop(heap) heapq.heappush(heap, end) return len(heap)这段代码的时间复杂度是O(n log n)空间复杂度O(n)。实操心得任务调度类的贪心问题排序键的选择非常关键。有时候按开始时间排有时候按结束时间排有时候按截止时间排具体用哪个取决于你要优化什么目标。我一般会先明确目标函数然后想“如果我是贪心的我每一步应该优先处理哪个任务”这个直觉往往能指向正确的排序键。4. 贪心算法的证明方法与验证技巧4.1 交换论证法最常用的证明套路交换论证法是证明贪心算法正确性最常用的方法它的核心思想是假设存在一个最优解它和贪心解在某一步做出了不同的选择你能不能通过交换把最优解变成贪心解并且不使结果变差。具体步骤通常是这样的假设贪心算法在第k步选择了元素x而某个最优解在第k步选择了元素y。构造一个新的解把最优解中的y替换成x。证明替换后的解仍然是最优的或者至少不比原来差。重复这个过程直到最优解和贪心解完全一致。以区间调度为例。假设最优解选的第一个区间是B贪心选的第一个区间是AA的结束时间不晚于B。因为A的结束时间不晚于B所以A和最优解中B之后的所有区间都不冲突因为那些区间的开始时间都大于等于B的结束时间而A的结束时间更早。所以我们可以用A替换B得到的新解仍然是最优的。这就证明了贪心选择是安全的。4.2 反例验证快速判断贪心是否失效在实际做题的时候你不可能每次都用严格的交换论证来证明贪心。更多时候你需要快速判断一个贪心策略是否可能失效。我的经验是先尝试构造反例如果构造不出来再尝试证明。构造反例的方法通常是找一个小规模的输入让贪心策略做出一个“看起来合理但实际不是最优”的选择。比如对于0-1背包你可以尝试让贪心选一个单位价值高但占用空间大的物品导致后面无法选其他高价值物品。如果你能找到反例那贪心策略就是错的赶紧换动态规划或者别的算法。如果找不到反例并且你能大致说清楚为什么贪心选择是安全的那就可以先用贪心写一版然后用暴力搜索或者动态规划对拍验证。4.3 对拍验证用暴力搜索检验贪心对拍是竞赛和工程中非常实用的验证技巧。具体做法是写一个暴力搜索的解法枚举所有可能的选择再写一个贪心解法然后随机生成大量小规模测试数据比较两个解法的输出是否一致。如果所有测试都一致那贪心解法大概率是正确的如果出现不一致那贪心解法就有问题。以区间调度为例暴力搜索可以用递归枚举所有子集检查是否互不重叠取最大的。贪心解法就是前面写的那个。随机生成n个区间n取1到10开始和结束时间取0到20的随机整数跑几千组测试如果都一致就可以比较放心了。注意对拍只能验证贪心在测试数据范围内是正确的不能替代严格证明。但在实际工程和竞赛中对拍已经足够帮你发现绝大多数错误。5. 贪心算法常见坑点与排查实录5.1 排序键选错导致结果偏差排序键选错是贪心算法最常见的坑。很多人凭直觉选了一个排序键代码跑出来结果不对但不知道错在哪里。比如区间调度问题如果你按开始时间排序然后贪心地选不重叠的区间结果可能不是最优的。反例区间A是[0, 100]区间B是[1, 2]区间C是[3, 4]。按开始时间排序是A、B、C贪心选A之后B和C都和A重叠所以只能选1个。但最优解是选B和C共2个。再比如任务调度问题如果你按任务所需时间排序优先做短任务可能也不是最优的。反例任务A截止时间100所需时间50任务B截止时间60所需时间30。按所需时间排序先做B再做AA在时间80完成没超过100B在时间30完成没超过60两个都按时完成。但如果任务A截止时间40所需时间50任务B截止时间60所需时间30。按所需时间排序先做B时间30完成再做A时间80完成超过40A失败。最优是先做A时间50完成超过40A还是失败。这个例子不好。换一个任务A截止时间50所需时间40任务B截止时间100所需时间30。按所需时间排序先做B时间30完成再做A时间70完成超过50A失败。最优是先做A时间40完成没超过50再做B时间70完成没超过100两个都成功。所以按所需时间排序是错的应该按截止时间排序。排查方法当你发现贪心结果不对时先检查排序键。问自己这个排序键能保证每一步的选择都是安全的吗如果不能换一个排序键试试。5.2 边界条件处理不当贪心算法的代码通常很短但边界条件很容易出错。常见的边界问题包括输入为空的情况。比如区间调度如果输入是空列表直接返回0不要试图访问intervals[0]。区间端点相等的情况。比如一个区间结束时间是5另一个区间开始时间是5它们算不算重叠通常不算因为一个在5结束一个在5开始可以无缝衔接。但具体要看题目定义有些题目要求严格不重叠有些允许端点重合。浮点数比较。分数背包涉及除法可能会有浮点误差。如果要求精确结果可以用分数类或者交叉相乘来比较。实操心得写贪心代码的时候先把边界情况列出来单独处理。比如空输入、只有一个元素、所有元素都相同、所有元素都冲突等等。这些情况虽然简单但最容易在面试或竞赛中丢分。5.3 贪心与动态规划混用导致逻辑混乱有时候一个问题看起来能用贪心但写完之后发现有些情况不对于是又加了一些动态规划的判断结果代码变得又长又乱还容易出错。我的建议是如果一个问题的贪心策略不能保证正确就果断放弃贪心直接用动态规划。不要试图在贪心框架里打补丁那样只会让代码更难维护。贪心和动态规划是两种不同的思路混在一起用往往得不偿失。当然有些问题确实需要结合两者比如一些复杂的调度问题可能需要先用贪心确定一个大致框架再用动态规划优化细节。但这种情况下你需要非常清楚每一步在做什么否则很容易写出错误的代码。5.4 常见问题速查表问题现象可能原因排查方法解决方案结果比预期差排序键选错检查排序键是否与贪心选择性质一致换排序键重新验证结果不稳定相同键值的元素顺序不确定检查排序是否稳定加次要排序键保证顺序确定边界情况报错空输入或单元素输入未处理单独测试边界情况加边界判断浮点误差涉及除法或浮点比较检查是否有精度问题用分数类或交叉相乘贪心失效问题不具备贪心选择性质尝试构造反例换动态规划或其他算法6. 贪心算法在实际工程中的应用场景6.1 任务调度与资源分配贪心算法在任务调度领域的应用非常广泛。比如在分布式系统中调度器需要把任务分配给不同的机器目标可能是最小化总完成时间、最大化吞吐量、或者保证公平性。很多调度策略本质上都是贪心的优先处理短任务、优先处理截止时间近的任务、优先处理资源需求小的任务等等。在实际工程中纯贪心策略往往不够因为现实约束比算法题复杂得多。但贪心提供了一个很好的起点你可以先实现一个贪心调度器观察它的表现然后根据实际需求逐步调整。6.2 数据压缩与编码霍夫曼编码是贪心算法在数据压缩领域的经典应用至今仍在很多压缩格式中使用。除了霍夫曼编码还有一些其他的贪心编码策略比如算术编码中的区间划分、游程编码中的合并策略等等。在实际使用中霍夫曼编码的变种很多比如自适应霍夫曼编码可以在不知道频率分布的情况下动态调整编码树。这些变种的核心思想仍然是贪心每次合并频率最小的两个节点。6.3 图论中的贪心应用图论中有很多经典的贪心算法比如最小生成树的Prim算法和Kruskal算法、单源最短路径的Dijkstra算法、以及一些近似算法。Prim算法的贪心策略是每次从已选节点集合出发选择一条连接到未选节点的最小权重边。Kruskal算法的贪心策略是每次选择权重最小且不构成环的边。Dijkstra算法的贪心策略是每次选择当前距离最小的未访问节点更新其邻居的距离。这些算法之所以能用贪心是因为它们的问题结构满足贪心选择性质和最优子结构。但要注意Dijkstra算法不能处理负权边因为负权边会破坏贪心选择性质。6.4 近似算法中的贪心策略对于很多NP难问题精确求解是不现实的这时候贪心算法常常被用来构造近似解。比如集合覆盖问题、旅行商问题、图着色问题等等都有基于贪心的近似算法。这些近似算法虽然不能保证最优但通常能保证一个近似比。比如集合覆盖的贪心算法能保证O(log n)的近似比也就是说贪心解的大小不超过最优解的log n倍。在实际工程中这样的近似比往往已经足够好了。7. 从刷题到实战我的贪心算法学习路径7.1 入门阶段从区间调度和找零钱开始如果你刚开始学贪心算法我建议从区间调度和找零钱这两个问题入手。它们足够简单能让你快速理解贪心的核心思想同时又能让你体会到“为什么贪心是对的”这个关键问题。区间调度的代码只有十几行但背后的交换论证值得反复琢磨。找零钱问题则能让你意识到贪心算法的正确性依赖于问题的具体结构换一套面额体系贪心可能就失效了。7.2 进阶阶段霍夫曼编码和分数背包掌握了基本思想之后可以看霍夫曼编码和分数背包。这两个问题的贪心策略稍微复杂一些但代码实现仍然很简洁。霍夫曼编码用到了优先队列分数背包用到了排序这些都是非常实用的编程技巧。这个阶段我建议你动手实现一遍不要只看不写。霍夫曼编码的堆操作、分数背包的排序和累加都有一些细节需要注意亲手写一遍才能记住。7.3 实战阶段对拍验证和反例构造当你觉得自己已经理解了贪心算法可以开始做一些有挑战性的题目。这个阶段最重要的技能是快速判断一个贪心策略是否可行以及用对拍验证自己的解法。我自己的习惯是拿到一个问题先想贪心策略如果能想到一个看起来合理的就写出来然后用暴力搜索对拍。如果对拍通过再尝试证明如果对拍失败就分析反例看看贪心策略哪里出了问题。这个过程反复练习之后你对贪心算法的直觉会越来越准。7.4 工程阶段把贪心思想融入系统设计在实际工程中贪心算法往往不是单独使用的而是作为系统设计的一部分。比如在调度系统中你可能先用贪心确定一个初始分配方案再用其他算法进行优化在压缩系统中你可能用贪心构建编码树再用其他技术进一步压缩。这个阶段的关键是理解贪心算法的适用边界知道什么时候该用它什么时候该换别的算法。贪心算法不是万能的但它在很多场景下是最简单、最高效的选择。8. 一些踩过的坑和实用建议贪心算法我踩过的坑不算少这里挑几个印象深刻的分享一下。第一个坑以为所有排序问题都能用贪心。有一次做一道任务调度题我按任务时长排序觉得短任务优先肯定没错结果对拍发现有些情况不对。后来才明白任务调度的目标函数不同排序键就不同。如果目标是最大化按时完成的任务数应该按截止时间排序如果目标是最小化平均完成时间应该按任务时长排序。排序键的选择取决于你要优化什么。第二个坑忽略贪心算法的前提条件。有一次做一道图论题我想用Dijkstra算法但图里有负权边结果算出来的距离是错的。后来改用Bellman-Ford算法才正确。这个坑让我记住每个贪心算法都有它的适用条件用之前一定要确认条件满足。第三个坑对拍数据规模太小。有一次我对拍的时候只生成了n5的数据跑了几百组都通过以为贪心没问题。结果提交之后发现n1000的时候有反例。后来我把对拍数据规模扩大到n20才发现了问题。对拍数据要覆盖各种规模不能只测小数据。第四个坑浮点数比较。分数背包问题里我用浮点数计算单位价值排序之后发现有些物品的顺序不稳定导致结果有微小差异。后来改用交叉相乘比较才解决了这个问题。涉及浮点数的贪心问题一定要小心精度。实用建议方面我总结了几条写贪心代码之前先用小规模例子手动模拟一遍确认贪心策略符合直觉。排序键的选择是贪心算法的核心选错了后面全错。对拍是验证贪心正确性的利器但要注意数据规模和边界情况。如果贪心策略找不到严格证明但对拍通过可以先用着但要留个心眼。贪心算法和动态规划不是对立的有些问题可以结合两者。最后再分享一个小技巧当你拿不准一个贪心策略是否正确时试着构造一个“贪心选择看起来合理但实际不是最优”的小例子。如果你能构造出来说明贪心不对如果构造不出来并且能大致说清楚为什么贪心选择是安全的那就可以先用贪心试试。这个方法我在实际做题和工程中用了很多次命中率相当高。