贪心、分治和动规

本文主要是介绍贪心、分治和动规，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

贪心、分治和动规是算法的入门思想，初学时容易混淆，故对比总结如下

两个概念

1. 重叠子问题：如果一个问题可以被分为若干个子问题，且这些子问题会重复出现，那么就称这个问题拥有重叠子问题
2. 最优子结构：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称这个问题拥有最优子结构

三个思想

1. 贪心：解决最优化问题，并希望由局部最优策略来推得全局最优结果。贪心算法适用的问题必须满足最优子结构
2. 分治：将原问题划分成若干个规模较小而结构与原问题相同或相似的子问题，然后分别解决这些子问题，最后合并子问题的解，即可得到原问题的解。分治必须拥有子问题，但不一定是重叠的子问题，且该问题不一定是最优化问题
3. 动态规划：一个问题必须拥有重叠子问题和最优子结构，才能使用动态规划去解决。动规有两个思路：①自顶向下（递归）——考虑重叠子问题-记录解（备忘录）②自底向上（递推）——考虑求解小问题顺序

对比

1. 分治与动规对比：

同：
分治和动态规划都是将问题分解为子问题，然后合并子问题的解得到原问题的解。
异：
分治——分解出的子问题是不重叠的，因此分治法解决的问题不拥有(或者并不用在意)重叠子问题，且

这篇关于贪心、分治和动规的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---