贪心 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 result

1.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 关键区别对比表

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 选择贪心算法的场景

1. 活动选择问题：如无重叠区间、用最少数量的箭引爆气球
2. 分配问题：如分发饼干、分发糖果
3. 可以分解为独立步骤：如买卖股票II、柠檬水找零
4. 覆盖问题：如跳跃游戏、监控二叉树

3.2 选择动态规划的场景

1. 需要保存中间结果：如最长递增子序列、编辑距离
2. 有多个约束条件：如背包问题、买卖股票含手续费
3. 子问题重叠明显：如斐波那契数列、爬楼梯
4. 需要回溯所有可能性：如通配符匹配、正则表达式匹配

4. 性能对比与优化

4.1 时间复杂度对比

4.2 空间复杂度对比

4.3 优化技巧

贪心算法优化：

1. 预处理时进行合适的排序
2. 使用双指针减少不必要的遍历
3. 利用数学性质简化判断条件

动态规划优化：

1. 状态压缩（如滚动数组）
2. 记忆化搜索替代DP表
3. 分析状态转移的依赖关系，减少不必要的计算

5. 实战建议与常见误区

5.1 贪心算法的常见误区

1. 盲目使用贪心：没有验证问题是否具有贪心选择性质
   • 反例：LeetCode 135.分发糖果必须用双向贪心
2. 错误排序：贪心通常需要先排序，但错误的排序标准会导致错误
   • 示例：LeetCode 452.用最少数量的箭引爆气球需要按结束位置排序
3. 忽略边界条件：如跳跃游戏中的初始条件处理

5.2 动态规划的常见误区

1. 错误的状态定义：导致状态转移方程复杂或错误
   • 建议：从简单子问题开始，逐步扩展
2. 不必要的状态存储：没有进行空间优化
   • 示例：斐波那契数列只需保存前两个状态
3. 混淆遍历顺序：如背包问题中物品和容量的遍历顺序

5.3 混合使用的情况

有些问题可以结合贪心和动态规划：

1. 贪心预处理+DP：先通过贪心减少问题规模
2. DP+贪心优化：在DP状态转移中使用贪心策略选择最优子结构

示例：LeetCode 968.监控二叉树，使用贪心思想确定摄像头放置策略，但实现上采用树形DP。