第12次内容

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

课前回顾

在第11次课中，我们进一步深化了对贪心算法的理解，实现了从“会用”到“懂用”的关键跃迁。课程围绕两个典型真题展开：跳跃游戏 II 和 森林中的兔子，引导我们从三个维度重新审视贪心策略的本质。

首先，我们从“能否到达”升级到“最少步数”的求解目标。跳跃游戏 II 不再只是判断终点是否可达，而是要求用最少的跳跃次数抵达终点。为此，我们采用了“在当前跳跃范围内，选择能跳得最远的位置作为下一跳落点”的贪心策略。这一策略不仅体现了“局部最优带来全局最优”的思想，更强调了为后续决策保留最大自由度的前瞻性设计。

其次，我们突破了贪心仅适用于连续结构（如数组、路径）的思维定式，通过“森林中的兔子”问题，将贪心思想成功迁移到离散分组与资源分配场景。问题的核心在于：对回答相同数量的兔子，尽可能填满每组容量（x+1）后再新开一组，从而以最少组数满足所有兔子的回答。这揭示了贪心的本质——在约束条件下做出最经济的选择。

最后，我们开始关注贪心策略的正确性证明。与之前直观的贪心选择不同，本课的策略需要更严密的逻辑支撑，例如“为什么选最远的落点一定最优？”这类问题促使我们思考贪心选择与最优子结构之间的耦合关系，从而建立起对算法正确性的深层理解。

通过本次课，我们不仅掌握了更复杂的贪心应用，更学会了如何抽象问题结构、识别贪心指标、并验证策略正确性，为后续面对更广泛的算法问题打下了坚实基础。

本次内容

本次总结

好的！结合你提供的两个网页内容（摆动序列 和 过河问题），我们可以提炼出贪心算法在这两类典型问题中的应用思路与共性启发。以下是一份结构清晰的总结：

🧠 贪心算法应用总结：摆动序列与过河问题

1. 摆动序列（Wiggle Subsequence）

目标：找出数组中最长的子序列，使得相邻元素的差值严格正负交替。
关键特征：需要“方向交替”（上升 → 下降 → 上升...），平台（差为0）无效。
贪心策略：只保留“转折点”（峰值和谷值），忽略单调段中的中间元素。

2. 过河问题（Crossing River）

目标：若干人过桥，每次最多两人，需带灯，速度由慢者决定，求最短总时间。
关键特征：时间由“最慢者”决定，组合策略影响总耗时。
贪心策略：在每一步选择当前最优的过桥组合（通常是“最快者来回送灯”或“最慢两人一起过”），通过比较两种经典策略（2A + Y + Z vs A + 2B + Z）选择更优者。

二、贪心法的思考路径

✅ 1. 识别问题是否具有“局部最优可导出全局最优”的性质

摆动序列：每个“方向转折点”都是对摆动长度的唯一贡献点，保留所有转折点即得最长序列。
过河问题：每轮送走最慢的两人时，选择当前耗时最少的方案，不会影响后续更优解。

✅ 2. 抽象出“关键决策点”

摆动序列 → 方向变化时刻（差值符号反转）
过河问题 → 如何送走最慢的两人（两种经典模式）

✅ 3. 设计状态或变量来追踪当前“最优状态”

摆动序列：用 prev_diff 或 up/down 状态记录上一次有效方向。
过河问题：维护当前未过河人员列表，每次贪心处理最慢两人。

✅ 4. 处理边界与特殊情况

摆动序列：全相等（返回1）、单调序列（返回2）
过河问题：1人、2人、3人时有特殊处理，不能套用通用公式

三、共性启发

🔹 启发1：贪心不是“直觉”，而是“结构洞察”

两个问题看似不同，但都依赖对问题本质结构的深刻理解：
- 摆动序列的本质是“方向交替” → 关注转折。
- 过河问题的本质是“最慢者拖累” → 关注如何最小化慢者带来的代价。

🔹 启发2：贪心常与“状态机”思想结合

用变量（如 prev_diff, is_up, 或当前剩余人数）记录当前状态，根据输入决定下一步动作。
这种“状态 + 决策”的模式是贪心实现的常见范式。

🔹 启发3：不要构造解，只需统计/模拟关键步骤

摆动序列：无需构造子序列，只需计数转折点。
过河问题：无需枚举所有方案，只需按贪心规则模拟过程。

🔹 启发4：贪心 vs 动态规划

摆动序列可用 DP（up[i], down[i]），但贪心更简洁。
过河问题若用 DP 状态复杂，贪心直接给出最优策略。
结论：当问题具备明显“局部最优即全局最优”结构时，优先考虑贪心。

🔹 启发5：贪心策略常需“比较多种局部方案”

过河问题的经典之处在于：每一步需在两种贪心策略中选更优者。
- 策略1：最快两人送最慢两人（A + 2B + Z）
- 策略2：最快一人来回送（2A + Y + Z）
这说明：贪心不等于“固定规则”，而是“在有限选项中选当前最优”。

四、总结一句话

贪心算法的核心，是在深入理解问题结构的基础上，设计出能够“每一步都做出当前最优选择”的策略，并确保这些局部最优能累加成全局最优。

摆动序列教会我们关注转折点，过河问题教会我们权衡组合代价——两者共同体现了贪心法“化繁为简、抓住本质”的强大能力。