05-分治算法秘籍

3.1.3　分治算法秘籍

分治法解题的一般步骤如下。

（1）分解：将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。

（2）治理：求解各个子问题。由于各个子问题与原问题形式相同，只是规模较小而已，而当子问题划分得足够小时，就可以用较简单的方法解决。

（3）合并：按原问题的要求，将子问题的解逐层合并构成原问题的解。

一言以蔽之，分治法就是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

在分治算法中，各个子问题形式相同，解决的方法也一样，因此我们可以使用递归算法快速解决，递归是彰显分治法优势的利器。