贪心 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 买卖股票最佳时机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): 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[i1]: candies[i] max(candies[i], candies[i1] 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 True4.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 -15. 性能对比与实战建议时间复杂度对比贪心算法通常为O(n)或O(nlogn)主要来自排序动态规划通常为O(n)或O(n²)取决于状态转移方程空间复杂度对比贪心算法通常为O(1)或O(n)如果需要额外存储动态规划通常为O(n)或O(n²)可优化为O(1)或O(n)实战建议首先分析问题是否具有贪心选择性质尝试构建反例验证贪心算法的正确性当贪心法不适用时考虑动态规划的三要素最优子结构状态转移方程边界条件对于特定问题如股票系列两种方法都可能适用但贪心通常更简洁在算法竞赛或面试中理解这两种算法的本质差异并能快速判断适用场景将显著提升解题效率。建议通过大量练习培养对问题特征的敏感度形成算法选择的直觉。
贪心 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 买卖股票最佳时机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): 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[i1]: candies[i] max(candies[i], candies[i1] 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 True4.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 -15. 性能对比与实战建议时间复杂度对比贪心算法通常为O(n)或O(nlogn)主要来自排序动态规划通常为O(n)或O(n²)取决于状态转移方程空间复杂度对比贪心算法通常为O(1)或O(n)如果需要额外存储动态规划通常为O(n)或O(n²)可优化为O(1)或O(n)实战建议首先分析问题是否具有贪心选择性质尝试构建反例验证贪心算法的正确性当贪心法不适用时考虑动态规划的三要素最优子结构状态转移方程边界条件对于特定问题如股票系列两种方法都可能适用但贪心通常更简洁在算法竞赛或面试中理解这两种算法的本质差异并能快速判断适用场景将显著提升解题效率。建议通过大量练习培养对问题特征的敏感度形成算法选择的直觉。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
