基本思想
分治法的設(shè)計思想是：將一個難以直接解決的大問題匆瓜，分割成一些規(guī)模較小的相同問題奔则，以便各個擊破蛮寂，分而治之。
分治策略是：對于一個規(guī)模為n的問題应狱，若該問題可以容易地解決（比如說規(guī)模n較小）則直接解決祠丝，否則將其分解為k個規(guī)模較小的子問題疾呻，這些子問題互相獨立且與原問題類型一致，遞歸地解這些子問題写半，然后將各子問題的解合并得到原問題的解岸蜗。
分治是很多高效算法的基礎(chǔ)，如排序算法(快速排序叠蝇，歸并排序)璃岳，傅立葉變換(快速傅立葉變換)……
分治與遞歸像一對孿生兄弟，經(jīng)常同時應用在算法設(shè)計之中悔捶，并由此產(chǎn)生許多高效算法铃慷。
使用場景
分治法所能解決的問題一般具有以下幾個特征：
1) 該問題的規(guī)模縮小到一定的程度就可以容易地解決
2) 該問題可以分解為若干個規(guī)模較小的相同問題蜕该，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)犁柜。
3) 利用該問題分解出的子問題的解可以合并為該問題的解；
4) 該問題所分解出的各個子問題是相互獨立的堂淡，即子問題之間不包含公共的子子問題馋缅。
第一條特征是絕大多數(shù)問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加绢淀；
第二條特征是應用分治法的前提它也是大多數(shù)問題可以滿足的萤悴，此特征反映了遞歸思想的應用；
第三條特征是關(guān)鍵皆的，能否利用分治法完全取決于問題是否具有第三條特征覆履，如果具備了第一條和第二條特征，而不具備第三條特征费薄，則可以考慮用貪心法或動態(tài)規(guī)劃法内狗。
第四條特征涉及到分治法的效率，如果各子問題是不獨立的义锥，則分治法要做許多不必要的工作柳沙，重復地解公共的子問題，此時雖然可用分治法拌倍，但一般用動態(tài)規(guī)劃法較好赂鲤。
實例
可使用分治法求解的一些經(jīng)典問題：
二分搜索噪径；合并排序、快速排序数初；大整數(shù)乘法找爱、Strassen矩陣乘法；棋盤覆蓋泡孩；線性時間選擇车摄；最接近點對問題；循環(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;
}
漢諾塔
在漢諾塔游戲中吮播，有三個分別命名為A、B眼俊、C的塔座意狠，幾個大小各不相同，從小到大依次編號得圓盤疮胖。最初环戈，所有得圓盤都在A塔座上，其中最大得圓盤在最下面澎灸，然后是第二大院塞，以此類推。
游戲的目的是 將所有的圓盤從塔座A移動到塔座B性昭，塔座C用來放置臨時圓盤迫悠，游戲的規(guī)則如下：
1、一次只能移動一個圓盤
2巩梢、任何時候都不能將一個較大的圓盤壓在較小的圓盤上面.
3创泄、除了第二條限制，任何塔座的最上面的圓盤都可以移動到其他塔座上
漢諾塔問題解決思想：
在解決漢諾塔問題時括蝠，事實上我們不是最關(guān)心圓盤1開始應該挪到哪個塔座上鞠抑，而是關(guān)心最下面的圓盤4。 當然忌警，我們不能直接移動圓盤4搁拙，但是圓盤4最終將從塔座A移動到塔座B。按照游戲規(guī)則法绵，在移動圓盤4之前的情況一定如下圖箕速。
四個圓盤從A移動到B，就要考慮如何將前三個圓盤從A移動到C朋譬，然后將圓盤4從A移動到B盐茎，最后將前三個圓盤從C移動到B。
但是上面的步驟可以重復利用徙赢！將問題規(guī)淖帜縮刑皆健：
三個圓盤從A移動到C，就要考慮如何將前兩個圓盤從A移動到B窑业，然后將圓盤3從A移動到C钦幔，最后將前兩個圓盤從B移動到C。
持續(xù)簡化這個問題常柄，最終我們將只需要處理一個圓盤從一個塔座移動到另一個塔座的問題鲤氢。
public class Moved {
private static int count = 1;
public static void main(String[] args) {
moved(4, "第一根柱子", "第二根柱子", "第三根柱子");
}
/**
* @param i 圓盤數(shù)量
* @param a 圓盤初始所在塔座
* @param b 圓盤將要移動到的塔座
* @param c 輔助圓盤移動的塔座
*/
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移動到C
disPaly(i, a, b); //將圓盤i由A移動到B
moved(i-1, c, b, a); //將i-1根圓盤由C移動到B
}
}
public static void disPaly(int i,String a,String b){
System.out.println("第"+count+"步：移動第"+i+"個塔從"+a+"到"+b);
count++;
}
}
運行結(jié)果：
第1步：移動第1個塔從第一根柱子到第三根柱子
第2步：移動第2個塔從第一根柱子到第二根柱子
第3步：移動第1個塔從第三根柱子到第二根柱子
第4步：移動第3個塔從第一根柱子到第三根柱子
第5步：移動第1個塔從第二根柱子到第一根柱子
第6步：移動第2個塔從第二根柱子到第三根柱子
第7步：移動第1個塔從第一根柱子到第三根柱子
第8步：移動第4個塔從第一根柱子到第二根柱子
第9步：移動第1個塔從第三根柱子到第二根柱子
第10步：移動第2個塔從第三根柱子到第一根柱子
第11步：移動第1個塔從第二根柱子到第一根柱子
第12步：移動第3個塔從第三根柱子到第二根柱子
第13步：移動第1個塔從第一根柱子到第三根柱子
第14步：移動第2個塔從第一根柱子到第二根柱子
第15步：移動第1個塔從第三根柱子到第二根柱子
