分治法的思想是将一个难以直接解决的大问题分割成一些规模较小的几个相似的问题来解决，分治法的求解过程是将整个问题分解成若干个小问题后分而治之，如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。分治法的求解通常会用到递归，通常会说分治法是一种找大规模问题与小规模问题关系的方法，是递归设计方法的一种具体策略。分治法的基本步骤在每一层递归上都有三个步骤： ① 分解：将原来的规模相对较