一、基本概念

专业的说法是：
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

分治法其实就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

二、基本特征

分治法所能解决的问题一般具有以下几个特征：

1) 大问题可分解性

该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

2) 子问题易解决性

该问题的规模缩小到一定的程度就可以容易地解决

3) 解可合并性

利用该问题分解出的子问题的解可以合并为该问题的解；

4) 子问题独立性

该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

三、基本特征详解

1) 大问题可分解性

第一条特征是使用分治法的前提，问题可分解，即是类似于数学归纳法，我们可以递归求解方程公式，然后根据方程公式设计出程序。

2) 子问题易解决性

第二条特征是要求我们判断大问题分解的为子问题的粒度，应该是易解决的。

3) 解可合并性

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，即子问题的解不能合并为大问题的解，那么我们不应该考虑分治法，而考虑其他算法。

4) 子问题独立性

第四条特征其实不是必须要满足，但是如果各子问题是不独立的，则分治法要重复地解公共的子问题，时间复杂度很高，此时虽然可用分治法，但一般用动态规划法较好。所以使用分治法，应该满足第四条特征，否则考虑其他算法。

四、分治法的基本步骤

step1 分解：

将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

step2 解决：

若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

step3 合并：

将各个子问题的解合并为原问题的解。

五、解决思路

类似于数学归纳法，找到解决本问题的求解方程公式，看大问题是否满足分治法的四个特征，然后根据方程公式设计递归程序。

1.在n较小时，写一写大问题的计算过程。

2.从计算过程中，抽象出递归方程。

3.看大问题是否满足分治法的四个特征

4.解决子问题的解。

5.子问题的解，合并出大问题的解。

六、经典问题

好记性不如烂笔头，有一些适用分治法的经典问题，可以帮我们不断强化分治法的解题思想。在解决问题时，希望大家可以注意判断题目的解决思路，看是否符合分治法的四个特征，这样不断强化，才能将算法掌握。

（1）二分搜索

（2）汉诺塔

（3）快速排序

（4）合并排序