1. 什么是贪心算法

⭐ 贪心算法总是做出在当前看来是最优的选择，也就是说，贪心算法并不从整体最优上考虑，所作的选择只是局部最优选择。

虽然贪心算法不是对所有问题都能得到整体最优解，但对很多问题都能产生整体最优解，或者最优解的很好的近似解。

2. 贪心算法的基本要素

动态规划问题的两个基本性质：

• 最优子结构
• 子问题重叠性质

而贪心算法的两个基本性质：

• 最优子结构

• 贪心选择性质

  贪心选择性质是指：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到

3. 贪心算法和动态规划算法

💡 贪心选择性质是贪心算法与动态规划算法的主要区别：

• 在动态规划算法中，每步所做的选择依赖于相关子问题的解，所以只有解决相关子问题后，才能做出选择。
• 而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择，再去解做出这个选择后产生的相应的子问题。也就是说，贪心算法所做的贪心选择可以依赖过去所做过的选择，但绝不依赖将来所作的选择，也不依赖子问题的解。

⭐ 正是由于这种差别，动态规划算法是自底向上的，而贪心算法是自顶向下的，以迭代的方式做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为规模更小的子问题。

4. 贪心策略在图算法中的应用

几个重要的图算法基本都使用了贪心策略，详细可见【图】相关章节

• 单源最短路径：Dijkstra 算法

• 最小生成树：

  • Prim 算法
  • Kruskal 算法