1、分治法的基本思想：将一个规模为n的问题分解为k个规模为较小的子问题，这些子问题互相独立且与原问题相同。递归求解这些子问题的解合并（构造）出原问题的解。

（1）分治算法的设计（分为三个阶段）：

• 分解阶段：将整个问题划分为多个子问题
• 递归求解阶段：递归调用正在设计的算法求解每个子问题
• 合并阶段：合并子问题的解，行程原始问题的解