基本思想
分治法的設(shè)計(jì)思想是：將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。
分治策略是：對(duì)于一個(gè)規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題類型一致，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。
分治是很多高效算法的基礎(chǔ)，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)……
分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。
使用場(chǎng)景
分治法所能解決的問題一般具有以下幾個(gè)特征：
1) 該問題的規(guī)?？s小到一定的程度就可以容易地解決
2) 該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
3) 利用該問題分解出的子問題的解可以合并為該問題的解；
4) 該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題。
第一條特征是絕大多數(shù)問題都可以滿足的，因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加；
第二條特征是應(yīng)用分治法的前提它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用；
第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動(dòng)態(tài)規(guī)劃法。
第四條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然可用分治法，但一般用動(dòng)態(tài)規(guī)劃法較好。
實(shí)例
可使用分治法求解的一些經(jīng)典問題：
二分搜索；合并排序、快速排序；大整數(shù)乘法、Strassen矩陣乘法；棋盤覆蓋；線性時(shí)間選擇；最接近點(diǎn)對(duì)問題；循環(huán)賽日程表；漢諾塔
二分查找
二分查找（基于有序數(shù)組）
/*基于遞歸的二分查找*/
public int rank(Key key,int lo,int hi)
{
if(hi<lo)
return lo;
int mid = lo+(hi-lo)/2;
int cmp = key.compareTo(keys[mid]);
if(cmp > 0)
return rank(key, mid+1, hi);
else if(cmp < 0)
return rank(key, lo, mid-1);
else return mid;
}
漢諾塔
在漢諾塔游戲中，有三個(gè)分別命名為A、B、C的塔座，幾個(gè)大小各不相同，從小到大依次編號(hào)得圓盤。最初，所有得圓盤都在A塔座上，其中最大得圓盤在最下面，然后是第二大，以此類推。
游戲的目的是 將所有的圓盤從塔座A移動(dòng)到塔座B，塔座C用來放置臨時(shí)圓盤，游戲的規(guī)則如下：
1、一次只能移動(dòng)一個(gè)圓盤
2、任何時(shí)候都不能將一個(gè)較大的圓盤壓在較小的圓盤上面.
3、除了第二條限制，任何塔座的最上面的圓盤都可以移動(dòng)到其他塔座上
漢諾塔問題解決思想：
在解決漢諾塔問題時(shí)，事實(shí)上我們不是最關(guān)心圓盤1開始應(yīng)該挪到哪個(gè)塔座上，而是關(guān)心最下面的圓盤4。 當(dāng)然，我們不能直接移動(dòng)圓盤4，但是圓盤4最終將從塔座A移動(dòng)到塔座B。按照游戲規(guī)則，在移動(dòng)圓盤4之前的情況一定如下圖。
四個(gè)圓盤從A移動(dòng)到B，就要考慮如何將前三個(gè)圓盤從A移動(dòng)到C，然后將圓盤4從A移動(dòng)到B，最后將前三個(gè)圓盤從C移動(dòng)到B。
但是上面的步驟可以重復(fù)利用！將問題規(guī)?？s?。?/p>
三個(gè)圓盤從A移動(dòng)到C，就要考慮如何將前兩個(gè)圓盤從A移動(dòng)到B，然后將圓盤3從A移動(dòng)到C，最后將前兩個(gè)圓盤從B移動(dòng)到C。
持續(xù)簡(jiǎn)化這個(gè)問題，最終我們將只需要處理一個(gè)圓盤從一個(gè)塔座移動(dòng)到另一個(gè)塔座的問題。
public class Moved {
private static int count = 1;
public static void main(String[] args) {
moved(4, "第一根柱子", "第二根柱子", "第三根柱子");
}
/**
* @param i 圓盤數(shù)量
* @param a 圓盤初始所在塔座
* @param b 圓盤將要移動(dòng)到的塔座
* @param c 輔助圓盤移動(dòng)的塔座
*/
public static void moved(int i, String a, String b, String c){
if(i == 1){
disPaly(1, a, b);
}else{
moved(i-1, a, c, b); //將i-1根圓盤由A移動(dòng)到C
disPaly(i, a, b); //將圓盤i由A移動(dòng)到B
moved(i-1, c, b, a); //將i-1根圓盤由C移動(dòng)到B
}
}
public static void disPaly(int i,String a,String b){
System.out.println("第"+count+"步：移動(dòng)第"+i+"個(gè)塔從"+a+"到"+b);
count++;
}
}
運(yùn)行結(jié)果：
第1步：移動(dòng)第1個(gè)塔從第一根柱子到第三根柱子
第2步：移動(dòng)第2個(gè)塔從第一根柱子到第二根柱子
第3步：移動(dòng)第1個(gè)塔從第三根柱子到第二根柱子
第4步：移動(dòng)第3個(gè)塔從第一根柱子到第三根柱子
第5步：移動(dòng)第1個(gè)塔從第二根柱子到第一根柱子
第6步：移動(dòng)第2個(gè)塔從第二根柱子到第三根柱子
第7步：移動(dòng)第1個(gè)塔從第一根柱子到第三根柱子
第8步：移動(dòng)第4個(gè)塔從第一根柱子到第二根柱子
第9步：移動(dòng)第1個(gè)塔從第三根柱子到第二根柱子
第10步：移動(dòng)第2個(gè)塔從第三根柱子到第一根柱子
第11步：移動(dòng)第1個(gè)塔從第二根柱子到第一根柱子
第12步：移動(dòng)第3個(gè)塔從第三根柱子到第二根柱子
第13步：移動(dòng)第1個(gè)塔從第一根柱子到第三根柱子
第14步：移動(dòng)第2個(gè)塔從第一根柱子到第二根柱子
第15步：移動(dòng)第1個(gè)塔從第三根柱子到第二根柱子
