贪心算法
求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择
- 分治算法的思路是将其分解成多个子问题，且求解每个子问题，然后按一定规则组合子问题（求解所有选择）
- 动态规划的思路是将其分解成多个子问题，且很多子问题相同，将子问题的解记录下来，一次遇到不必重复求解（求解所有选择）
- 贪心算法是这样的：作出局部最优的选择，希望这样的选择能导致全局最优，也就是说只需求解一个子问题（只求解一个选择）
如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。
此性质是能否应用动态规划和贪心方法的关键要素
当应用与贪心算法时，我们通常使用更为直接的最优子结构