1.贪心算法

贪心算法是就问题而言，选择当下最好的选择，而不从整体最优考虑，通过局部最优希望导致全局最优。

贪心算法的要素

1）贪心选择性质：可以通过局部最优选择来构造全局最优解。换言之，直接做出在当前问题中看来最优的选择，而不必考虑子问题的解。

2）最优子结构：一个问题的最优解包含其子问题的最优解。

贪心算法的设计步骤：

1）将最优化问题转换为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解

2）证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的

3）证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。

示例：背包问题，均分纸牌，最大整数

作者：半路和尚怎么出家
链接：https://www.jianshu.com/p/48a6bdfccff1
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.递归与分治

3.动态规划

4.回溯法

5.分支界限法