在算法设计里，“分治”（Divide & Conquer）是一类非常经典、也非常实用的思想。许多著名算法，例如归并排序、快速排序、最近点对、快速傅里叶变换（FFT）等，背后都在用分治的套路。
这篇文章不讲某一个具体题目，而是总结分治算法的一般思路，并给出一个可以"套用"的通用伪代码模板，方便写代码时直接代入。
一、什么是 Divide & Conquer？
分治（Divide & Conquer），直译就是"分而治之"：把一个规模较大的问题拆成若干个规模更小、形式相同的子问题，分别解决这些子问题后，再把它们的解合并，得到原问题的解。
它的三个关键词可以概括为：
- Divide（分）：拆分问题
- Conquer（治）：递归求解子问题
- Combine（合）：合并子问题的解
只要一个问题满足下面这几个特征，就比较适合用分治：
- 原问题可以拆分成若干个规模更小但结构相同的子问题。
- 子问题之间相对独立，也就是彼此之间关联不太大。
- 有一个明确的"最小规模"，当规模足够小时，可以不用再拆，直接解决。
- 能设计出一个高效的合并步骤，把子问题的答案拼回到原问题的答案上。
如果"分"之后合并的代价太大，或者拆出来的子问题彼此强耦合（高度依赖），那么分治就不一定划算，甚至可能比简单的暴力还慢。
二、分治算法的一般套路
从实现角度看，绝大多数分治算法都可以抽象成对一个"问题实例"的递归函数调用。伪代码的逻辑大致都是下面这四步：