分治算法
分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 k 个规模较小，并且结构与原问题相似的子问题，递归 地解决这些子问题，然后再合并其结果，就得到原问题的解。
这个定义看起来有点类似递归的定义。关于分治和递归的区别：
- 分治算法是一种处理问题的思想;
- 递归是一种编程技巧。
比较经典的应用就是 归并排序（Merge Sort） 以及 快速排序（Quick Sort） 等。我们来从归并排序理解分治思想，归并排序就是将待排序数组不断二分为规模更小的子问题处理，再将处理好的子问题合并起来。
算法思想
总体思想：
- 将要求解的较大规模的问题分割成
k 个更小规模的子问题。 - 对这
k 个子问题分别求解。如果子问题的规模仍然不够小，则再划分为 k 个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 - 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
算法特征
分治所能解决的问题一般具有以下几个特征：
- 该问题的规模缩小到一定的程度 可以直接求解
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有 最优子结构性质
- 利用该问题分解出的子问题的解 可以合并 为该问题的解
- 该问题所分解出的各个子问题是相互独立的，即 子问题之间不包含公共的子问题
说明：
- 第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
- 第二条特征是应用分治算法的前提，他也是大多数问题可以满足的，此特征反映了 递归思想 的引用；
- 第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心算法或动态规划法；
- 第四条特征涉及到 分治的效率，如果各子问题是不独立的，则分治要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治，但 一般用动态规划较好。
设计思路
设计过程分为三个步骤：
实际上，分治算法一般都比较适合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：
- 拆分 Divide：将原问题拆分成若干个子问题；
- 解决 Conquer：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
- 合并 Merge：将各个子问题的解合并，形成原问题的解。
分治的执行步骤可以分为三个阶段，即划分数据阶段、递归处理阶段和综合合并阶段。有些问题的划分阶段时间费用较多，有些问题则合并阶段的时间费用较多。
依据分治算法设计程序时的思维过程：
实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。
- 一定是先找到最小问题规模时的求解方法
- 然后考虑随着问题规模增大时的求解方法
- 找到求解的递归函数式后（各种规模或因子），设计递归程序即可。
经典问题
斐波那契数列
经典问题