分治思想

分治法的设计思想是，将一个难以解决的大问题，分割成一些规模较小的相同问题，这些子问题互相独立且与原问题相同，以便逐个击破，分而治之。所以使用分治策略时，常常会用到递归（不断地分治）。

递归

要想领会分治的思想，就要先理解递归，“递归”这个词可以拆分成两个字来解释

• 递：有传递的意思，也就是递归算法所对应的方法，要有参数，并且自己调用自身时，也要传递参数。
• 归：是指自身调用自身是有限度的，最后会“归一”

但需要注意的是，递归算法的运行效率很低，非常耗费内存

斐波那契数列就是一个常见的使用递归的例子

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式

F(n)=F(n-1)+F(n-2)，其中f(1)=f(2)=1;

分治策略的解题步骤

1. 将原问题划分或归结为较小规模的子问题
2. 递归或迭代求解每个子问题
3. 将子问题综合得到原问题的解

注意：

1. 子问题与原始问题性质完全一样
2. 子问题间可彼此独立的求解
3. 递归停止时，子问题可直接求解

算法实例

• 二分检索算法
• 棋盘覆盖问题
• 二分归并排序