分治法

分治法

“分治”顾名思义：分而治之。《孙子兵法》有云：“凡治众如治寡，分数是也。”将一个难题，分割成一些规模较小的相同子问题，分而治之，以便于各个击破。然后再利用这些子问题的解，求出原问题的解。

分治策略：将一个规模为n的问题，若可直接解决（比如n较小），则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题合并得到原问题的解。这种算法设计策略叫做分治法。

分治法的基本思想：将规模n的问题分解为各个子问题，用递归地形式去解决这些子问题，合并这些子问题解。

分治法所能解决的问题一般具有一下几个特征:

• 该问题的规模缩小到一定的程度就可以容易地解决；

• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

• 利用该问题分解出的子问题的解可以合并为该问题的解；

• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

能否利用分治法完全取决于问题是否具有最后一条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。