贪心算法 (Greedy Algorithms)

1. 核心思想

在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的。

• 局部最优 $\rightarrow$ 全局最优。

2. 适用场景

• 问题具有贪心选择性质。
• 问题具有最优子结构。

3. 经典问题

• 活动选择问题 (Activity Selection)
• 霍夫曼编码 (Huffman Coding)
• Prim 和 Kruskal 最小生成树算法
• Dijkstra 最短路径算法

推荐资源

• Runoob: 贪心算法