分治，动态规划与贪心的区别
最近在准备软件设计师的考试，下午的试题有一道数据结构与算法分析的题目，一时搞不懂分治，动态规划与贪心这三种算法的区别。
总体看一下三种算法的比较：
分治法
描述：
两部分组成
分（divide）：递归解决较小的问题
治（conquer）：然后从子问题的解构建原问题的解
三个步骤
1、分解（Divide）：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
2、解决（Conquer）：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
3、合并（Combine）：将各个子问题的解合并为原问题的解。
四个适用条件
1、该问题的规模缩小到一定的程度就可以容易地解决；
2、该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3、利用该问题分解出的子问题的解可以合并为该问题的解；
4、该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
（上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。）
例如：
归并排序（merge sort）是一个典型分治法的例子。其对应的直观的操作如下：
分解：将n个元素分成各含n/2个元素的子序列；
解决：用合并排序法对两个子序列递归地排序；
合并：合并两个已排序的子序列以得到排序结果。
如果想多了解十大排序算法的，可参考另一篇博客：
https://blog.csdn.net/hello_cmy/article/details/96290862
动态规划：
基本思想
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
四个步骤：
描述最优解的结构
递归定义最优解的值
按自底向上的方式计算最优解的值
由计算出的结果构造一个最优解
适合采用动态规划方法的最优化问题中的两个要素：**最优子结构和重叠子问题。 **
- 最优子结构：
如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。
- 重叠子问题：
适用于动态规划求解的最优化问题必须具有的第二个要素是子问题的空间要很小，也就是用来求解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。对两个子问题来说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，则它们是重叠的。
分治法：各子问题独立
动态规划：各子问题重叠
最长公共子序列就是使用了动态规划思想，还有找零钱等问题。有兴趣的可以找找看。
贪心算法
对许多最优化问题来说，采用动态规划方法来决定最佳选择有点“杀鸡用牛刀”了，只要采用另一些更简单有效的算法就行了。贪心算法是使所做的选择看起来都是当前最佳的，期望通过局部最优选择来产生出一个全局最优解。贪心算法对大多数优化问题来说能产生最优解，但也不一定总是这样的。
基本要素
贪心选择
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。
最优子结构
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题 [2] 。
思想
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止 。
参考文章：
参考链接：https://blog.csdn.net/zwhlxl/article/details/44086105
参考链接：https://www.jianshu.com/p/660bc387500c