# Divide and Conquer - 分治法

在計算機科學中，分治法是一種很重要的演算法。分治法即『分而治之』，把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併。這個思想是很多高效演算法的基礎，如排序演算法（快速排序，合併排序）等。

## 分治法思想

分治法所能解決的問題一般具有以下幾個特徵：

1. 問題的規模縮小到一定的程度就可以容易地解決。
2. 問題可以分解爲若干個規模較小的相同問題，即該問題具有**最優子結構**性質。
3. 利用該問題分解出的子問題的解可以合併爲該問題的解。
4. 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。

分治法的三個步驟是：

1. 分解（Divide）：將原問題分解爲若乾子問題，這些子問題都是原問題規模較小的實例。
2. 解決（Conquer）：遞歸地求解各子問題。如果子問題規模足夠小，則直接求解。
3. 合併（Combine）：將所有子問題的解合併爲原問題的解。

分治法的經典題目：

1. 二分搜索
2. 大整數乘法
3. Strassen矩陣乘法
4. 棋盤覆蓋
5. 歸並排序
6. 快速排序
7. 循環賽日程表
8. 河內塔
