分治

定义

将原问题分成若干个子问题，分别独立解决后将结果合并。

即“分而治之，各个击破”

基本思想

将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些问题，然后将各个子问题的解合并成原问题的解。

分治适合什么问题

1. 问题缩小到一定的规模就可以容易的解决
2. 问题能够分解成若干个规模较小的、解决方案一样的独立的子问题
3. 子问题的解可以合并为原问题的解

Attention

• 第三条完全决定了问题能不能使用分治法
• 如果不满足第三条，但是满足前两条，则可以考虑贪心算法或者动态规划算法

分治法解题的特征

该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好(例如记忆化搜索是分治转化为动归的一个经典, 要注意)。 — Updated on 2022-04-16 09:24:00

与递归的区别

参见递归-区别-分治