下载掌阅APP，畅读海量书库
立即打开
在现实生活中，对什么样的问题才能使用分治算法解决呢？想要使用分治算法，需要满足以下三个条件：
（1）原问题可被分解为若干规模较小的相同子问题；
（2）子问题相互独立；
（3）子问题的解可以合并为原问题的解。
分治算法求解秘籍如下。
（1）分解：将原问题分解为若干规模较小、相互独立且与原问题形式相同的子问题。
（2）治理：求解各个子问题。由于各个子问题与原问题形式相同，只是规模较小，所以当子问题划分得足够小时，就可以用较简单的方法解决。
（3）合并：按原问题的要求，将子问题的解逐层合并成原问题的解。
一言以蔽之，分治算法是将一个难以直接解决的大问题分割成一些规模较小的相同问题，以便各个击破、分而治之。在分治算法中，各个子问题形式相同，解决方法也一样，因此可以使用递归算法快速解决。所以，递归是彰显分治算法优势的利器。