贪心算法与动态规划的区别是什么？
贪心算法和动态规划都是常见的解决问题的算法思想，它们在一定情况下可以解决类似的问题，但在实际应用中有着明显的区别。
- 贪心算法（Greedy Algorithm）: 贪心算法是一种在每一步选择中都采取当前状态下最优的选择，从而希望最终能够得到全局最优解的算法思想。贪心算法通常适用于那些每一步都可以做出一个局部最优选择，并且这些局部最优解能够积累起来得到全局最优解的问题。贪心算法的优点是简单、高效，适用于一些特定类型的问题，例如最小生成树、最短路径等。
举例说明：假设有一组硬币面值数组{1, 3, 5, 7, 9}，需要凑出金额15，如果采用贪心算法，每次选择面值最大的硬币，即9、5、1，最终凑出15需要的硬币数量为3枚。
- 动态规划（Dynamic Programming）: 动态规划是将原问题分解成子问题进行求解，通过记录子问题的解避免重复计算，从而达到优化时间复杂度的目的。动态规划适用于那些具有重叠子问题和最优子结构特点的问题。动态规划的优点是能够解决一些复杂问题，但相对复杂，需要设计状态转移方程和存储中间结果。
举例说明：背包问题是动态规划常见的应用场景之一，给定一组物品的重量和价值，背包容量为C，要求装入背包的物品总价值最大。动态规划可以通过状态转移方程来递推求解，具体算法可参考01背包、完全背包、多重背包等。
总结： 贪心算法和动态规划的主要区别在于贪心算法每一步都做出局部最优选择，并希望最终得到全局最优解，适用于某些特定类型的问题；动态规划则是通过记录中间结果避免重复计算，适用于具有最优子结构的问题。在实际应用中，需要根据问题的特点选择合适的算法思想来解决。
