Chapter 15 Greedy Algorithms
理论基础
本质
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
应用场景
通过局部最优解得到整体最优解，即题目中没有明显的关联性。一般能够拆分子问题，并且子问题的最优解能够得到原问题的最优解。在某些情况下，贪心并不一定能够推导出全局最优解。而在特定场景下，贪心的效率可能会高于动态规划。
思路
- 确定贪心策略
- 确定遍历顺序
- 求解每个子问题的最优解
- 将子问题的最优解合并为原问题的最优解
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
通过局部最优解得到整体最优解，即题目中没有明显的关联性。一般能够拆分子问题，并且子问题的最优解能够得到原问题的最优解。在某些情况下，贪心并不一定能够推导出全局最优解。而在特定场景下，贪心的效率可能会高于动态规划。