目录

动态规划和贪心算法

动态规划

贪心算法

两者之间的区别

---

动态规划和贪心算法

是两种经典的算法设计策略，它们各自具有独特的特点和适用场景。

动态规划

动态规划是一种将复杂问题分解为更简单子问题的求解方法。它特别适用于那些具有重叠子问题和最优子结构特性的问题。动态规划的核心在于两个主要概念：状态定义和状态转移。

• 状态定义：涉及如何描述问题的各个阶段或步骤。
• 状态转移：涉及如何从一个状态到达另一个状态，通常通过状态转移方程来描述。

在动态规划中，我们会保存每个子问题的解，以避免重复计算。这通常通过使用记忆化（Memoization）或表格法（Tabulation）来实现。

举例说明：

<