贪心性质
用贪心算法解决的题目需要满足以下性质：
- 最优子结构：一个问题的最优解包含其子问题的最优解。
- 贪心选择性：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
对比动态规划
DP满足
- 最优子结构：一个问题的最优解包含其子问题的最优解。
- 重叠子问题：在问题的求解过程中，很多子问题的解将被多次使用。
贪心算法设计
- 设计贪心选择方法：
- 贪心选择方法
- 剩余子问题
- 证明：对于 1 中贪心选择来说 所求解的问题具有最优子结构
- 证明：对于 1 中贪心选择算法来说 所求解的问题具有贪心选择性
- 归纳法：证明在每一步做得都比其它算法好 从而最终产生了一个最优解
- 交换论证法：在保证最优性不变前提下 从一个最优解逐步替换 最终得到贪心算法的解
- 按照 1 中设计的贪心选择方法设计算法