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

「解决一个问题需要多个步骤，每一个步骤有多种选择」这样的描述我们在「回溯算法」「动态规划」算法中都会看到。它们的区别如下：

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

对于不同的求解目标和不同的问题场景，需要使用不同的算法。动态规划与贪心算法的区别，我们画在下面这张图里。

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

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

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

<aside> 📌 能用贪心算法的一定能用动态规划，能用动态规划的不一定能用贪心算法。

</aside>