贪心算法、回溯算法、动态规划的区别

• 回溯算法：需要记录每一个步骤、每一个选择，用于回答所有具体解的问题
• 动态规划：需要记录的是每一个步骤、所有选择的汇总至（最大、最小或者计数）
• 贪心算法：由于适用的问题，每一个步骤只有一种选择，一般而言只需要记录与当前步骤相关的变量的值

动态规划需要考虑原问题的所有的子问题

贪心算法每一次只需要考虑一个子问题，并且通常是自底向上求解

可以使用贪心算法的问题需要满足的条件

• 最优子结构：规模较大的问题的解由规模较小的子问题的解组成，区别于动态规划，可以使用贪心算法的问题规模较大的问题的解只由其中一个规模较小的子问题的解决定
• 无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果
• 贪心选择性质：从局部最优解可以得到全局最优解

对「最优子结构」和「无后效性」的理解同「动态规划」，「贪心选择性质」是「贪心算法」最需要关注的内容。