1. 概述
在面对算法问题时，我们通常可以采用多种方法来解决。其中最常被问到的问题之一就是：贪心算法（Greedy Approach） 与 动态规划（Dynamic Programming） 之间的区别。
本文将从理论和实践两个层面，解释这两种算法的核心思想，并通过具体示例进行对比分析。
2. 贪心算法
2.1 核心思想
贪心算法是一种每一步都选择当前状态下最优解的策略，希望通过局部最优解（local optimal）来达到全局最优解（global optimal）。
✅ 适用前提：局部最优选择能导出全局最优解。
❌ 风险：如果问题不具备该特性，贪心算法可能无法得到正确解。
2.2 示例：活动选择问题
问题描述：给定一组活动，每个活动有开始时间和结束时间，一个人最多能参与多少个互不重叠的活动？
贪心策略：每次选择结束时间最早的活动。
✅ 证明：选择最早结束的活动可以为后续活动留下更多时间，因此该策略可以得到全局最优解。
algorithm MaxNonIntersectingActivitiesGreedy(activities):
// INPUT
// activities = 活动列表
// OUTPUT
// result = 最大不重叠活动数
sortOnEndTime(activities)
currentEndTime <- 负无穷
result <- 0
for each activity in activities:
if currentEndTime < activity.startTime:
result <- result + 1
currentEndTime <- activity.endTime
return result
时间复杂度分析：
- 排序：
O(n log n) - 遍历：
O(n) - 总体复杂度：✅
O(n log n)
经典应用：Dijkstra 算法、Prim 算法。
2.3 反例：0/1 背包问题
贪心算法无法解决 0/1 背包问题，因为局部最优无法保证全局最优。
比如：一个物品单位价值高但体积太大，可能被贪心选中，但导致后续无法装下其他更优组合。
3. 动态规划
3.1 核心思想
动态规划是一种优化递归回溯的算法策略，主要解决重叠子问题和指数级时间复杂度的问题。
✅ 核心机制：将已经计算过的状态结果保存下来，避免重复计算。
两种实现方式：
- 自顶向下（Top-down）：递归 + 记忆化（memoization）
- 自底向上（Bottom-up）：迭代 + DP 表格
✅ 优势：将指数级复杂度优化为多项式级别，并保证最优解。
3.2 示例：活动选择问题的 DP 解法
我们重新来看活动选择问题，使用动态规划解决。
状态定义：dp[i] 表示从第 i 个活动开始能选择的最大活动数。
状态转移：
dp[i] = max(dp[i+1], 1 + dp[next])
其中：
dp[i+1]：不选第 i 个活动1 + dp[next]：选第 i 个活动，next是下一个可选活动
实现思路：
- 按开始时间排序
- 倒序遍历活动
- 使用二分查找快速定位下一个可选活动
时间复杂度：
- 排序：
O(n log n) - 遍历 + 二分查找：
O(n log n) - 总体复杂度：✅
O(n log n)
3.3 反例：旅行商问题（TSP）
虽然旅行商问题可以使用动态规划解决，但由于状态空间巨大（O(n * 2^n)），在实际中并不适合。
❌ 原因：子问题数量过多，状态难以压缩，DP 表格占用内存大。
4. 贪心 vs 动态规划 对比
| 特性 | 贪心算法 | 动态规划 |
|---|---|---|
| 核心思想 | 每步选当前最优 | 保存子问题结果 |
| 是否最优解 | 仅当局部最优导出全局最优时成立 | ✅ 保证最优解 |
| 时间复杂度 | ✅ 通常更低（多项式） | ❗ 通常更高（多项式） |
| 空间复杂度 | ✅ 更优 | ❗ 需要额外空间保存状态 |
| 适用场景 | 问题具备贪心选择性质 | 存在重叠子问题 |
| 典型例子 | Dijkstra、Prim | 0/1 背包、最长递增子序列 |
📌 总结：如果能用贪心解决，优先使用贪心；否则考虑 DP。
5. 总结
本文对比了贪心算法与动态规划的核心思想、适用场景和典型示例：
- 贪心算法适合局部最优导出全局最优的问题，效率高但适用性有限；
- 动态规划适合存在重叠子问题的场景，能保证最优解但时间和空间成本较高。
📌 建议：
- 面对新问题时，先尝试贪心解法；
- 若贪心无法奏效，再考虑优化递归方案，使用动态规划。
📌 踩坑提醒：
- 不要盲目使用贪心，一定要证明局部最优是否能导出全局最优；
- DP 虽好，但不要在状态空间爆炸时强行使用。