一、简介
分治算法从字面上理解就是分而治之，即把一个复杂的大问题分成若干个相同或者相似的子问题，在把子问题划分成更多小问题，直到最后子问题是简单一下就能解出来为止；然后开始把简单的子问题向上合并，最终得到大问题的解。
举个例子：16枚硬币，其中有一个假币，假币的重量和真币的重量不一样，请问比较多少次能够找出假币。首先我们把这个大问题分成两个小问题，随机选择8枚硬币作为第一组，剩下来的8枚硬币作为第二组。利用仪器判断假币在那一堆里。在剩下的那组里再取出两组4枚，进行称重，依此类推。最后，找出假币。此过程如图1所示
二、适用条件
采用分治法解决的问题一般具有的特征如下：
1. 问题的规模缩小到一定的规模就可以较容易地解决；
2. 问题可以分解为若干个规模较小的模式相同的子问题，即该问题具有最优子结构性质；
3. 合并问题分解出的子问题的解可以得到问题的解；
4. 问题所分解出的各个子问题之间是独立的，即子问题之间不存在公共的子问题；
三、步骤
1. 划分步：把输入的问题划分为k个子问题，并尽量使这k个子问题的规模大致相同。
2. 治理步：当问题的规模大于某个预定的值n0时，治理步由k个递归调用组成。
3. 组合步：组合步把各个子问题的解组合起来，它对分治算法的实际性能至关重要，算法的有效性很大地依赖于组合步的实现。
分治法的关键是算法的组合步。究竟应该怎样合并，没有统一的模式，因此需要对具体问题进行具体分析，以得出比较好的合并算法。
四、实现框架
对于一个规模为n的问题，若该问题可以轻而易举地解决，则直接进行解决，否则将其分为k个规模较小的问题，这些子问题相互独立，递归地解决这些子问题，最后将这些问题合并，从而得到原题的解。
分治算法伪代码：
{
if(|p|<=n0)
{
resolve(P);
return;
}
for(int i=1; i<=k; i++)
{
yi=Divide_and_Conquer(Pi);
}
T=MERGE(y1,y2,…,yk);
return T;
}感谢阅读！