动态规划与贪心法的异同

动态规划和贪心算法是两种常用的算法设计方法，它们在解决问题时有着不同的策略和适用场景。

相同点：
1. **优化目标**：两者都是为了解决最优化问题，即找到问题的全局最优解或局部最优解。
2. **递归思想**：动态规划通常涉及到将大问题分解为子问题，然后通过保存中间结果避免重复计算，这是一种自底向上的递归过程。

不同点：
1. **问题分解**：动态规划强调子问题重叠，通常有明确的最优子结构；而贪心算法则是每一步选择局部最优解，但不保证整体上是最佳的，不考虑所有可能的子问题。
2. **决策顺序**：动态规划会保存所有子问题的解，以便于后续使用；贪心算法则是“一次选择，一次最优”，不会回溯或保存中间状态。
3. **适用范围**：动态规划适用于那些具有最优子结构且存在重叠子问题的问题，如背包问题、最长公共子序列等；贪心算法则适用于某些问题可以直接通过局部最优解得到全局最优解，比如霍夫曼编码、最小生成树等，但并非所有情况下都能保证得到全局最优。