Divide and Conquer
分治（Divide and Conquer），字面上的解释是 分而治之，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。[1]
流程
分治算法的通用流程如下：
- 分解原问题为结构相同的子问题
- 分解到某个容易求解的边界后，进行递归求解
- 将子问题的解合并成原问题的解
使用场景
分治算法能解决的问题一般有如下特征：
- 该问题的规模缩小到一定程度就能轻易解决
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题
子问题一定要相互独立
如果各子问题是不独立的，则分治法要重复地解公共的子问题，也就做了许多不必要的工作。此时虽然也可用分治法，但一般用动态规划较好。
Divide-and-conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.[2]