贪心 vs 动态规划：LeetCode 5道同题异构对比，详解选择依据与性能差异-育师

贪心 vs 动态规划：5道LeetCode同题异构对比与算法选择策略

1. 算法本质差异与选择逻辑

当面对LeetCode中的最优化问题时，我们常常需要在贪心算法和动态规划之间做出选择。这两种算法看似相似，实则存在根本性差异：

贪心算法的核心在于局部最优推导全局最优，它通过每一步的贪婪选择构建解决方案，特点是：

自顶向下解决问题
无后效性（当前选择不影响后续子问题）
通常时间复杂度更低（O(n)或O(nlogn)）

动态规划则采用状态转移方程解决问题，其特征为：

自底向上构建解决方案
具有最优子结构性质
需要存储中间状态（可能带来更高空间复杂度）

关键判断标准：问题是否具有贪心选择性质。若能证明局部最优能导致全局最优，则贪心算法适用；若需要比较所有可能的子问题组合，则必须使用动态规划。

2. 经典题目对比分析

2.1 摆动序列（LeetCode 376）

贪心解法：

def wiggleMaxLength(nums): if len(nums) < 2: return len(nums) prev_diff = nums[1] - nums[0] count = 2 if prev_diff != 0 else 1 for i in range(2, len(nums)): curr_diff = nums[i] - nums[i-1] if (curr_diff > 0 and prev_diff <= 0) or (curr_diff < 0 and prev_diff >= 0): count += 1 prev_diff = curr_diff return count

时间复杂度：O(n)
空间复杂度：O(1)

动态规划解法：

def wiggleMaxLength(nums): if not nums: return 0 up = down = 1 for i in range(1, len(nums)): if nums[i] > nums[i-1]: up = down + 1 elif nums[i] < nums[i-1]: down = up + 1 return max(up, down)

时间复杂度：O(n)
空间复杂度：O(1)（优化后）

对比结论：

贪心法通过统计峰值数量直接解决问题
动态规划维护了两个状态变量（上升/下降序列长度）
此问题中贪心法更直观，但两者时间复杂度相同

2.2 买卖股票最佳时机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): dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]) return dp[-1][1]

时间复杂度：O(n)
空间复杂度：O(n)（可优化为O(1)）

对比结论：

贪心法利用"所有上升区间累加"的特性
动态规划模拟了状态转移过程
贪心法更简洁高效，但动态规划框架更通用

3. 算法选择决策矩阵

问题特征	贪心算法适用性	动态规划适用性
具有贪心选择性质	✅ 优先选择	⚠️ 可能过度设计
需要比较所有子问题组合	❌ 无法保证最优	✅ 必须使用
时间复杂度要求严格	✅ 通常更优	⚠️ 可能较高
空间复杂度限制严格	✅ 通常更优	⚠️ 需要状态存储
问题可分解为独立子问题	✅ 表现良好	⚠️ 可能不必要

4. 贪心可行但动规不推荐的情况

4.1 分发糖果（LeetCode 135）

虽然可用动态规划解，但贪心的双向遍历更高效：

def candy(ratings): n = len(ratings) candies = [1] * n # 左到右遍历 for i in range(1, n): if ratings[i] > ratings[i-1]: candies[i] = candies[i-1] + 1 # 右到左遍历 for i in range(n-2, -1, -1): if ratings[i] > ratings[i+1]: candies[i] = max(candies[i], candies[i+1] + 1) return sum(candies)

4.2 跳跃游戏（LeetCode 55）

贪心法通过维护最大覆盖范围解决问题：

def canJump(nums): max_reach = 0 for i in range(len(nums)): if i > max_reach: return False max_reach = max(max_reach, i + nums[i]) return True

4.3 加油站（LeetCode 134）

贪心法通过一次遍历确定起点：

def canCompleteCircuit(gas, cost): total_tank = curr_tank = start = 0 for i in range(len(gas)): total_tank += gas[i] - cost[i] curr_tank += gas[i] - cost[i] if curr_tank < 0: start = i + 1 curr_tank = 0 return start if total_tank >= 0 else -1