分治法的思想是将一个难以直接解决的大问题分割成一些规模较小的几个相似的问题来解决，分治法的求解过程是将整个问题分解成若干个小问题后分而治之，如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。分治法的求解通常会用到递归，通常会说分治法是一种找大规模问题与小规模问题关系的方法，是递归设计方法的一种具体策略。分治法的基本步骤在每一层递归上都有三个步骤：

①　　分解：将原来的规模相对较大的问题分解为规模较小的、相互独立的、与原问题形式相同的子问题。

②　　解决：若子问题规模较小而容易解决则直接解决，否则再继续分解为更小的子问题，直到容易解决。

③　　合并：将已求解的各个子问题的解，逐步合并成原问题的解。

当求解一个输入规模为n并且取值比较大的问题时，可以使用分治法提高解决问题的效率。

-The idea is to divide and conquer difficult to directly solve a big problem is divided into some smaller number of similar problems to solve, divide and conquer the whole problem solving process is divided into several small problems of divide and rule, if the decomposition sub-problems are too big, relatively speaking, you can divide and conquer strategy of repeated use of these sub-problems into smaller sub-problems of the same type, until the child produces easy to solve the problem, if necessary, to gradually merge the sub-solution of the problem, to be the solution. Divide and conquer method is usually used for solving recursive, divide and conquer is usually said to find large-scale problems is a problem with the relationship between small-scale method is a recursive design specific strategies. The basic steps to divide and conquer recursion on each floor has three steps:

① decomposition: the relative size of the original large problem into smaller, independent, original proble