分治法

基本思想

• 将问题分解为若干规模较小的同构子问题
• 分解直到子问题的规模足够小，直接求解
• 合并子问题的解得到原问题的解

应用

分治排序

• 归并排序
• 快速排序

减治法

基本思想

• 将问题分解为多个子问题
• 只选取一个规模足够小的有效子问题
• 解决该问题，得到解，放弃其他子问题

应用

• 二分法
• 欧几里得算法（gcd）

变治法

基本思想

• 改变问题的形式，使其更易于求解

对象翻转

将问题的目标对象和输入对象进行翻转

• 集合子集和：每个子集元素和 $\rightarrow$ 每个元素所在子集数
• 区间最值：每个区间最值 $\rightarrow$ 每个最值生效区间

实例简化

对输入实例做预处理，使之变成更规整、更有序、更易处理的形式。

• 预排序
• 预计算
• 唯一性消除

表示变换

不改变问题本身，而是换一种数据结构或数学表示来存储/操作数据，使得算法效率质变。

• 堆状数组取极值
• 并查集表示连通性
• 线性递推的矩阵表示

问题规约

将原问题转化为另一个已知可解的问题，用已知算法的解来得到原答案。

• 最大子段和 $\rightarrow$ 前缀和数组 + 最小前缀和