概念
分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
分治算法是一种处理问题的思想。
递归实现
怎么实现一个分治算法呢，其实，大部分的算法，都是递归来实现的。实现分治算法的递归，需要三个条件：
- 分解：将原问题分解成一系列子问题；
- 解决：递归地求解各个子问题，若子问题足够小，则直接求解；
- 合并：将子问题的结果合并成原问题。
其实就是这三个步骤。
环境
分治算法，能解决的问题，一般都满足几个条件：
- 原问题与分解成的小问题具有相同的模式；
- 原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别，等我们讲到动态规划的时候，会详细对比这两种算法；
- 具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
- 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。
我们可以针对我们遇到的问题，一个一个来对应。
代码模版
# Python def divide_conquer(problem, param1, param2, ...): # recursion terminator if problem is None: print_result return # prepare data data = prepare_data(problem) subproblems = split_problem(problem, data) # conquer subproblems subresult1 = self.divide_conquer(subproblems[0], p1, ...) subresult2 = self.divide_conquer(subproblems[1], p1, ...) subresult3 = self.divide_conquer(subproblems[2], p1, ...) … # process and generate the final result result = process_result(subresult1, subresult2, subresult3, …) # revert the current level states
小结
分治是一种很高效的算法
分治算法，分而治之，很常用了。现实生活中，也经常遇到，我们要好好的去使用这些算法，提高我们的生活效率。OK，翻篇。
