贪心常见题型

  1. 按某种顺序排序后，然后逐个取(sort，多关键字排序，重载小于符号)
  2. 每次取集合中的最大/最小，更新答案（使用priority_queue）

贪心在最优子结构的问题中尤为有效（最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。）

贪心与dp的区别，贪心对每个子问题的解决方案都做出选择，不能回退。dp会保存以前的运算结果，并根据以前的结果进行选择，有回退功能。

有的时候，贪心并不是正确的，比如01背包问题，贪心就会出错。贪心问题特别像逻辑题，方法很简单，但是证明却很难。考场上，不需要会证明。

贪心法证明的常见方法