贪心 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 买卖股票的最佳时机 IILeetCode 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 跳跃游戏 IILeetCode 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时间复杂度买卖股票IIO(n)O(n)跳跃游戏IIO(n)O(n²)最大子数组和O(n)O(n)4.2 空间复杂度对比题目贪心空间复杂度DP空间复杂度买卖股票IIO(1)O(n) → 可优化到O(1)跳跃游戏IIO(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。