分治算法
分治的关键不是“递归”两个字，而是把原问题拆成若干个同类子问题，分别解决后还能正确合并回来。
核心思路
分治通常盯三件事：
- 怎么拆。
- 什么时候停。
- 怎么合。
如果只能拆、不能高效合并，或者子问题之间大量重叠，那就不一定适合纯分治，可能更像 动态规划。
高频专题
排序类
归并排序（Merge Sort）
分：从中间拆开治：分别排好左右两半合：线性归并成一个有序数组
快速排序（Quick Sort）
分：围绕 pivot 划分治：递归处理左右区间合：原地完成，不需要显式归并
数组与查找类
最大子数组和（Maximum Subarray）
- 典型的“左边最优、右边最优、跨中点最优”三合一
寻找两个正序数组的中位数
- 本质上是规模缩减式分治
数组中的逆序对
- 利用归并时的相对顺序顺手统计答案
数学类
快速幂（Fast Power）
- 指数减半，时间从
O(n)降到O(log n)
大整数乘法（Karatsuba算法）
- 用更巧妙的拆分减少乘法次数
矩阵乘法（Strassen算法）
- 了解思想即可，工程中不一定常用
几何与经典题
最近点对问题
- 经典分治几何题
汉诺塔（Tower of Hanoi）
- 它更像“用最纯的递归去理解分治结构”
怎么判断能不能分治
满足下面三条时，通常值得往分治想：
- 原问题和子问题长得足够像。
- 子问题之间基本独立。
- 合并阶段不会比求子问题本身更贵。
分治 vs 动态规划
| 特性 | 分治算法 | 动态规划 |
|---|---|---|
| 子问题 | 相互独立 | 有重叠 |
| 重复计算 | 无 | 有（需要记忆化） |
| 求解方向 | 自顶向下 | 自底向上或记忆化 |
| 典型例子 | 归并排序 | 背包问题 |
Go 模板
func solve(problem Problem) Answer {
if smallEnough(problem) {
return directSolve(problem)
}
left, right := split(problem)
leftAns := solve(left)
rightAns := solve(right)
return merge(leftAns, rightAns)
}易错点
分治题最容易写成“看起来像递归，实际上没有高效利用分治结构”。
- 递归出口不清晰会直接爆栈。
- 合并逻辑通常才是整题最难的部分。
- 有些题分治能做，但不是最优，比如最大子数组和常用解其实是 DP。
- 快排类题要特别注意最坏情况和 pivot 选择。
相关主题
返回：算法学习导航