贪心 vs 动态规划：从 3 道 LeetCode 经典题看算法选择与性能差异
贪心 vs 动态规划：从 3 道 LeetCode 经典题看算法选择与性能差异
在算法学习过程中，贪心算法和动态规划（DP）是两种非常重要的解题思路。很多同学在刷题时常常困惑：什么时候该用贪心？什么时候该用动态规划？这两种算法在性能上又有何差异？本文将通过三道经典LeetCode题目，深入分析这两种算法的本质区别、适用场景和性能表现。
1. 算法思想本质对比
贪心算法和动态规划都是解决最优化问题的常用方法，但它们的思考方式有着根本的不同。
1.1 贪心算法的核心思想
贪心算法采用自顶向下的思考方式，在每一步都做出当前看起来最优的选择，希望这些局部最优选择能够导致全局最优解。贪心算法通常不需要考虑子问题的解，也不依赖于将来的选择。
贪心算法有效的两个关键性质：
- 贪心选择性质：每一步的局部最优选择能导致全局最优解
- 最优子结构：问题的最优解包含其子问题的最优解
# 贪心算法的典型结构 def greedy_algorithm(): sort_input() # 通常需要先排序 result = 0 for item in sorted_items: if is_valid(item): # 根据贪心策略判断 result += process(item) return result1.2 动态规划的核心思想
动态规划采用自底向上的思考方式，通过将问题分解为相互重叠的子问题，存储子问题的解来避免重复计算。动态规划通常需要考虑所有可能的子问题解，然后做出选择。
动态规划适用的两个关键条件：
- 重叠子问题：问题可以被分解为多个重复的子问题
- 最优子结构：问题的最优解可以由子问题的最优解构造出来
# 动态规划的典型结构 def dynamic_programming(): dp = initialize_dp_array() # 初始化DP数组 for i in range(1, n): for j in range(m): dp[i] = optimal_choice(dp[i-1], dp[j]) # 根据状态转移方程更新 return dp[n-1]1.3 关键区别对比表
| 特性 | 贪心算法 | 动态规划 |
|---|---|---|
| 思考方向 | 自顶向下 | 自底向上 |
| 子问题 | 不保存子问题解 | 保存子问题解 |
| 时间复杂度 | 通常O(n)或O(nlogn) | 通常O(n²)或O(nm) |
| 空间复杂度 | 通常O(1) | 通常O(n)或O(nm) |
| 证明难度 | 需要严格证明 | 状态转移方程明确 |
| 适用问题 | 具有贪心选择性质 | 具有最优子结构 |
2. 经典题目双解法对比
下面我们通过三道经典题目，分别展示贪心和动态规划的解法，并分析它们的差异。
2.1 买卖股票的最佳时机 II（LeetCode 122）
问题描述：给定股票每天的价格，可以多次买卖，但必须卖出后才能再买，求最大利润。
贪心解法
def maxProfit(prices): profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1] return profit贪心思路：只要今天价格比昨天高就卖出，累积所有正收益。
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
动态规划解法
def maxProfit(prices): n = len(prices) dp = [[0] * 2 for _ in range(n)] dp[0][0] = -prices[0] # 持有股票 dp[0][1] = 0 # 不持有股票 for i in range(1, n): # 第i天持有：前一天已持有 或 今天买入 dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) # 第i天不持有：前一天不持有 或 今天卖出 dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]) return dp[-1][1]DP思路：用dp[i][0]和dp[i][1]分别表示第i天持有/不持有股票的最大收益。
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)（可优化到O(1)）
对比分析：
- 贪心解法更简洁高效，但需要问题具有贪心选择性质
- DP解法更通用，可以解决更复杂变种（如含手续费、冷冻期等）
2.2 跳跃游戏 II（LeetCode 45）
问题描述：给定非负整数数组，每个元素代表在该位置可以跳跃的最大长度，求到达最后位置的最小跳跃次数。
贪心解法
def jump(nums): jumps = 0 current_end = 0 farthest = 0 for i in range(len(nums)-1): farthest = max(farthest, i + nums[i]) if i == current_end: jumps += 1 current_end = farthest return jumps贪心思路：在每一步的覆盖范围内选择能跳最远的位置作为下一跳。
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
动态规划解法
def jump(nums): n = len(nums) dp = [float('inf')] * n dp[0] = 0 for i in range(n): for j in range(1, nums[i] + 1): if i + j < n: dp[i + j] = min(dp[i + j], dp[i] + 1) return dp[-1]DP思路：dp[i]表示到达位置i的最小跳跃次数，遍历每个位置更新能到达的位置。
复杂度分析：
- 时间复杂度：O(n²)
- 空间复杂度：O(n)
对比分析：
- 贪心解法明显更优，利用了问题的特殊性质
- DP解法会超时，仅作为理解问题使用
2.3 最大子数组和（LeetCode 53）
问题描述：给定整数数组，找到具有最大和的连续子数组。
贪心解法
def maxSubArray(nums): current_sum = max_sum = nums[0] for num in nums[1:]: current_sum = max(num, current_sum + num) max_sum = max(max_sum, current_sum) return max_sum贪心思路：当前子数组和为负数时，从下一个元素重新开始计算。
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
动态规划解法
def maxSubArray(nums): n = len(nums) dp = [0] * n dp[0] = nums[0] for i in range(1, n): dp[i] = max(nums[i], dp[i-1] + nums[i]) return max(dp)DP思路：dp[i]表示以nums[i]结尾的最大子数组和。
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)（可优化到O(1)）
对比分析：
- 两种解法本质相同，只是表述方式不同
- 贪心版本更简洁，空间效率更高
3. 算法选择决策流程
如何判断一个问题该用贪心还是动态规划？以下是决策流程图：
开始 │ ├─ 问题可以分解为子问题 → 是 → 子问题重叠？ → 是 → 使用动态规划 │ │ │ ↓ │ 否 → 具有贪心选择性质？ → 是 → 使用贪心算法 │ │ │ ↓ │ 否 → 可能需要回溯或其他方法 │ └─ 问题不能分解为子问题 → 考虑其他算法（如排序、双指针等）3.1 选择贪心算法的场景
- 活动选择问题：如无重叠区间、用最少数量的箭引爆气球
- 分配问题：如分发饼干、分发糖果
- 可以分解为独立步骤：如买卖股票II、柠檬水找零
- 覆盖问题：如跳跃游戏、监控二叉树
3.2 选择动态规划的场景
- 需要保存中间结果：如最长递增子序列、编辑距离
- 有多个约束条件：如背包问题、买卖股票含手续费
- 子问题重叠明显：如斐波那契数列、爬楼梯
- 需要回溯所有可能性：如通配符匹配、正则表达式匹配
4. 性能对比与优化
4.1 时间复杂度对比
| 题目 | 贪心时间复杂度 | DP时间复杂度 |
|---|---|---|
| 买卖股票II | O(n) | O(n) |
| 跳跃游戏II | O(n) | O(n²) |
| 最大子数组和 | O(n) | O(n) |
4.2 空间复杂度对比
| 题目 | 贪心空间复杂度 | DP空间复杂度 |
|---|---|---|
| 买卖股票II | O(1) | O(n) → 可优化到O(1) |
| 跳跃游戏II | O(1) | O(n) |
| 最大子数组和 | O(1) | O(n) → 可优化到O(1) |
4.3 优化技巧
贪心算法优化：
- 预处理时进行合适的排序
- 使用双指针减少不必要的遍历
- 利用数学性质简化判断条件
动态规划优化：
- 状态压缩（如滚动数组）
- 记忆化搜索替代DP表
- 分析状态转移的依赖关系，减少不必要的计算
5. 实战建议与常见误区
5.1 贪心算法的常见误区
- 盲目使用贪心：没有验证问题是否具有贪心选择性质
- 反例：LeetCode 135.分发糖果必须用双向贪心
- 错误排序：贪心通常需要先排序，但错误的排序标准会导致错误
- 示例：LeetCode 452.用最少数量的箭引爆气球需要按结束位置排序
- 忽略边界条件：如跳跃游戏中的初始条件处理
5.2 动态规划的常见误区
- 错误的状态定义：导致状态转移方程复杂或错误
- 建议：从简单子问题开始，逐步扩展
- 不必要的状态存储：没有进行空间优化
- 示例：斐波那契数列只需保存前两个状态
- 混淆遍历顺序：如背包问题中物品和容量的遍历顺序
5.3 混合使用的情况
有些问题可以结合贪心和动态规划：
- 贪心预处理+DP：先通过贪心减少问题规模
- DP+贪心优化：在DP状态转移中使用贪心策略选择最优子结构
示例：LeetCode 968.监控二叉树，使用贪心思想确定摄像头放置策略，但实现上采用树形DP。