3.3.1 分治算法基础

在编程过程中，经常遇到处理数据相当多、求解过程比较复杂、直接求解会比较耗时的问题。在求解这类问题时，可以采用各个击破的方法。具体做法是：先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解。如果这些子问题还是比较大，可以继续把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治算法的基本思想。

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

（1）分解，将要解决的问题划分成若干个规模较小的同类问题。

（2）求解，当子问题划分得足够小时，用较简单的方法解决。

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