第3章 递归与分治法

在现实中，有很多较为复杂的问题，如果直接解决这些问题会比较困难，但是这些问题可以被分解为n个规模较小而结构与原问题相似的子问题，通过解决这些相对简单的子问题，得到子问题的解，然后将子问题的解合并，就得到原问题的解。以上这个过程就是通过分治策略来解决问题。讲到分治，就必须提到递归，它们就像一对孪生兄弟，经常同时应用在算法设计中，并由此产生许多高效的算法。本章将详细介绍递归与分治的思想以及它们的应用。