第11次内容

周子力大约 6 分钟教学文档算法设计与分析

课前回顾

在之前的课程中，我们通过两个经典问题深入体会了贪心法的设计思想和应用优势：一个是“买卖股票的最佳时机 II”，另一个是“跳跃游戏”。

这两个问题虽然背景不同，但都展现了贪心算法的精髓——在每一步做出当前看来最优的选择，希望通过一系列局部最优的选择达到全局最优解。

在“买卖股票”问题中，我们的贪心策略是：只要明天的价格比今天高，就今天买入、明天卖出。我们不追求判断“最低点买入、最高点卖出”的完美时机，而是抓住每一个能赚钱的机会。这种“见好就收”的策略，最终累加起来恰好就是最大利润。这体现了贪心法的局部最优决策思想。

而在“跳跃游戏”中，我们没有尝试枚举所有可能的跳跃路径（那会非常低效），而是采用了更聪明的方法：维护一个变量 max_reach，表示当前能够到达的最远位置。我们遍历每一个可达的位置，并不断用 i + nums[i] 来更新这个最远边界。一旦发现某个位置 i 超出了 max_reach，说明无法继续前进，直接返回 false；如果 max_reach 能覆盖到最后一个位置，则返回 true。这个方法的关键洞察在于，我们不需要知道具体怎么跳，只需要知道“能跳多远”。这体现了贪心法的状态简化与最优子结构特性。

通过这两个例子，我们可以总结出贪心算法的一些重要性质：

贪心选择性质：所做出的每一步选择都是当前状态下的最佳选择。
最优子结构：一个问题的最优解包含其子问题的最优解。
高效性：通常时间复杂度较低，如上述两个问题均为 O(n)。
正确性依赖于问题特性：贪心法并非万能，其正确性需要严格的数学证明或逻辑推理来保证。

掌握贪心法，关键在于培养对问题本质的洞察力：能否将一个看似复杂的问题，通过一个巧妙的“贪心指标”（如累计利润、最远可达位置）进行简化？希望同学们课后多加练习，体会这种“大道至简”的算法之美。

本次内容

真题讲解

本次总结

通过两个真题，加深对贪心算法的理解。

跳跃游戏II：通过贪心算法，找到最短的跳跃路径。
森林中的兔子：通过贪心算法，计算最少需要多少只兔子。

本节课在上一课“贪心法基础认知”的基础上，实现了对贪心算法理解的深度深化与思维跃迁，主要体现在以下三个维度：

1. 从“能否到达”到“最少步数”：贪心策略的精细化与目标重构

上一课的“跳跃游戏I”关注的是可行性判断——“是否能到达终点”，贪心策略是“维护最大可达边界”。而本课的“跳跃游戏II”则将目标升级为最优性求解——“最少需要多少跳”。

这标志着我们对贪心的理解从被动验证转向了主动优化。我们不再满足于知道“能走多远”，而是要在每一步都做出能最小化总步数的决策。我们通过“在当前跳跃范围内，选择能跳得最远的那个位置作为下一跳的落点”这一策略，实现了局部最优（每跳最大化延伸）→ 全局最优（总跳数最少） 的闭环。这揭示了贪心算法中一个更深刻的洞察：最优解往往隐藏在“扩展能力最大化”的贪心指标中，而非简单的可达性判断。

2. 从“连续结构”到“离散分组”：贪心思想在非传统场景中的迁移与抽象

“森林中的兔子”一题打破了我们对贪心算法“只适用于数组或路径”的固有印象。问题本质是：一群兔子回答“有多少同伴和我一样颜色”，我们要推断最少需要多少只兔子。

这看似是统计问题，实则是分组与归并的贪心优化。我们发现：若某只兔子说“有x只和我一样”，那么这x+1只兔子构成一个颜色组。若有多只兔子都说“x”，我们不能无脑合并，而应贪心地将它们尽可能分到同一组中（最多容纳x+1只），超出的才开新组。这种“按回答值分组、组内容量受限、最小化组数”的思路，将贪心思想从“线性扫描”成功迁移到了集合划分与资源分配的场景，极大拓展了贪心的应用边界。

这告诉我们：贪心的核心不是形式，而是“在约束下做最经济的选择”。只要能抽象出“资源容量”与“需求匹配”的关系，贪心就可能适用。

3. 从“单指标决策”到“动态约束下的策略选择”：贪心正确性证明的思维深化

上一课的两个问题，其贪心选择的正确性相对直观（利润可累加、边界可扩展）。而本课的两个问题，尤其是“跳跃游戏II”，其贪心选择的正确性需要更严密的逻辑支撑：为什么“在当前可达范围内选能跳最远的点”一定是最优的？

这引导我们思考：贪心算法的正确性，往往依赖于问题的最优子结构与贪心选择性质的耦合。在跳跃II中，每一步的“最远跳跃”不仅扩大了可达范围，还为后续决策保留了最大自由度，从而保证了后续仍能做出最优选择。这不再是“见好就收”，而是“为未来留足空间”的前瞻性贪心。

同样，在“森林中的兔子”中，我们不是随便分组，而是在“每组容量上限”的硬约束下，用最少组数容纳所有需求——这本质上是装箱问题的贪心近似，其正确性依赖于“相同回答值的兔子优先同组”这一策略能避免资源浪费。

✅ 总结：本课对贪心算法的深化

维度	上一课	本课深化
目标	判断可行性（是否能）	求解最优性（最少/最多）
场景	连续序列、路径	离散分组、资源分配
策略	维护边界/累加收益	动态选择最优落点、组内容量优化
思维层级	局部最优 → 全局可行	局部最优 → 全局最优（需证明）
核心洞察	抓住每一个机会	在约束下做最经济、最前瞻的选择

本课标志着我们从“会用贪心”迈向了“懂贪心”：我们不仅知道什么时候用贪心，更理解了为什么这个贪心策略是对的，以及如何在看似无关的问题中抽象出贪心的本质结构。这种从“现象模仿”到“模式提炼”的跃迁，正是算法思维进阶的关键一步。