1. 概述
在本篇教程中，我们将深入探讨两种非常流行的算法设计范式：分治法（Divide and Conquer） 和 动态规划（Dynamic Programming）。
我们会先介绍它们的基本思想，然后分别通过一个经典示例来说明其工作原理，最后总结它们之间的核心差异。
2. 分治法的基本思想
分治法的核心思想是：将一个复杂的问题分解为若干个规模较小的子问题，分别求解这些子问题，最后将子问题的解合并，得到原问题的解。
整个过程通常分为三个阶段：
- 分解（Divide）：将原问题拆解为若干个子问题。
- 求解（Conquer）：递归地求解各个子问题。
- 合并（Combine）：将子问题的解合并为原问题的解。
下图展示了分治法的执行流程：
分治法通常能显著降低算法的时间复杂度，是许多高效算法的基础。
3. 分治法的示例：二分查找
一个典型的分治法应用是 二分查找（Binary Search）。我们来看它的实现逻辑。
问题描述
给定一个有序数组，我们需要查找某个目标值是否存在于该数组中。如果存在，返回 true，否则返回 false。
分治思路
- 将数组一分为二；
- 判断目标值位于哪一半；
- 递归地在该半部分中继续查找；
- 直到找到目标值或确定不存在。
示例图解
下图展示了查找值 14 的过程：
可以看到，我们不需要遍历整个数组，只需要访问其中一部分元素，因此时间复杂度为 O(log n)。
Java 示例代码
public boolean binarySearch(int[] arr, int target, int left, int right) {
if (left > right) return false;
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return true;
} else if (arr[mid] < target) {
return binarySearch(arr, target, mid + 1, right);
} else {
return binarySearch(arr, target, left, mid - 1);
}
}
✅ 优点：代码简洁，效率高
❌ 限制：必须保证数组是有序的
4. 动态规划的基本思想
动态规划也是一种将大问题分解为子问题的策略，但与分治法不同的是，子问题之间存在重叠（Overlapping Subproblems）。
动态规划的关键在于：
- 状态定义：明确每个子问题的含义
- 状态转移方程：找出子问题之间的关系
- 记忆化（Memoization）或表格化（Tabulation）：保存子问题的解，避免重复计算
它通常用于求解最优化问题，例如最长公共子序列、背包问题等。
5. 动态规划示例：斐波那契数列
一个经典的动态规划问题是 斐波那契数列（Fibonacci Sequence）。
问题描述
斐波那契数列定义如下：
$$ F(n) = F(n-1) + F(n-2) $$ 初始值为： $$ F(0) = 0, \quad F(1) = 1 $$
分治法 vs 动态规划
使用普通的递归（分治）实现会存在大量重复计算：
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
时间复杂度高达 O(2^n)，效率极低。
而使用动态规划可以避免重复计算：
动态规划实现（表格法）
int fib(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
图解执行流程
✅ 优点：时间复杂度降至 O(n)，空间复杂度 O(n)（可进一步优化为 O(1)）
⚠️ 注意：不要直接使用递归，否则效率极低
6. 分治法 vs 动态规划：对比总结
| 特性 | 分治法 | 动态规划 |
|---|---|---|
| 是否递归 | ✅ 多数为递归 | ❌ 多数为非递归（表格法） |
| 子问题是否重叠 | ❌ 独立 | ✅ 重叠 |
| 是否保存子问题结果 | ❌ 不保存 | ✅ 保存 |
| 时间复杂度 | ⏱️ 通常较高 | ⏱️ 通常较低 |
| 应用场景 | 排序、查找等 | 最优化问题（如最长子序列、背包问题） |
7. 总结
虽然分治法和动态规划在思想上有相似之处，但它们在实现机制和适用场景上有显著差异：
- ✅ 分治法适用于子问题相互独立、结构相似的问题，如排序、查找；
- ✅ 动态规划适用于子问题重叠且存在最优子结构的问题，如最优化问题、组合问题；
- ⚠️ 选择哪种方法取决于问题的性质和子问题之间的关系；
- ❗ 在实际开发中，务必根据问题特征选择合适策略，避免“为用而用”。
在算法设计中，理解这两种范式的本质，能帮助我们写出更高效、更优雅的代码。