LeetCode中的贪心与动态规划混合题

在算法学习的进阶之路上，贪心算法与动态规划常被视为两种核心的解题范式。然而，LeetCode题库中有一类颇具挑战性的题目，它们并非单纯归属于某一类别，而是巧妙地将贪心的直觉与动态规划的严谨融为一体。这类“贪心与动态规划混合题”要求解题者不仅要有敏锐的最优子结构洞察力，还需用动态规划的框架去验证和实现贪心的策略，是提升算法综合能力的绝佳试金石。

理解这类问题的关键在于辨析两种策略的本质。动态规划通过保存子问题的解来避免重复计算，其核心是状态定义与状态转移方程，往往能求得全局最优解，但可能带来较高的时间复杂度。贪心算法则每一步都采取当前看来最优的选择，期望以此导向全局最优，效率高但需要严格的正确性证明。混合题的出现，常常是因为问题本身具有这样的特质：我们可以通过贪心策略确定最优解的某些“形状”或决策顺序，但剩余部分仍需动态规划进行精确计算。

一个经典的范例是“435. 无重叠区间”。此题要求移除最少数量的区间，使剩余区间互不重叠。纯粹的动态规划思路是按终点排序后，定义`dp[i]`为前i个区间中能构成的最大不重叠区间数，状态转移需遍历之前所有区间，复杂度为O(n2)。然而，其贪心策略亦十分显著：优先选择结束最早的区间，为后续区间留下更多空间。实际上，该贪心策略可以直接解决问题，无需DP。但若题目变体为“给定每个区间一个权重，求最大权重和的不重叠区间集合”，则演变为经典的“加权区间调度”问题。此时，贪心（仅按结束时间选择）可能失效，必须结合动态规划：在按结束时间排序后，`dp[i]`表示考虑前i个区间的最大权重和，转移时通过二分查找找到最后一个不与当前区间重叠的区间j，比较`dp[i-1]`与`dp[j] + weight[i]`。这里，排序体现了贪心（决策顺序）的思想，而DP则负责精确计算最优值。

更典型的混合题是“452. 用最少数量的箭引爆气球”。问题可转化为寻找最多的不重叠区间组（每一组可被一箭射穿），其本质与“无重叠区间”高度相似。解题时，我们同样先按区间终点（气球右边界）升序排序，这是贪心思想的体现：尽早结束区间以释放箭支。但具体计数过程，可以视为一个隐性的动态规划：当前箭簇的结束点`end`，只有当新区间的起点大于`end`时，才需增加箭数并更新`end`。这个过程记录了状态（当前箭簇的覆盖范围）并根据新状态决策，是贪心策略在DP思维框架下的高效实现。

另一道值得深入剖析的题目是“376. 摆动序列”。它要求找到最长摆动子序列的长度，其中相邻数字的差正负交替。纯粹的动态规划需要定义两个状态数组`up[i]`和`down[i]`，分别表示以第i个元素结尾且最后呈上升或下降趋势的最长摆动序列长度。状态转移需考察之前所有元素，复杂度为O(n2)。然而，我们可以用贪心思想优化其过程：只需遍历一次，维护当前序列的“趋势”状态。当我们遇到连续上升或下降时，只有在趋势发生实际改变时才增加序列长度。这本质上是一种状态机DP的贪心实现：我们将DP状态（当前趋势）压缩为几个变量，在遍历中直接进行转移和决策，将复杂度降至O(n)。这种“贪心优化DP”正是混合题的精髓之一。

再如“968. 监控二叉树”，此题要求在二叉树节点放置摄像头，覆盖所有节点。它需要结合树形DP与贪心策略。自底向上的DP状态定义较为复杂（0:未被覆盖，1:有摄像头，2:被覆盖）。但确定状态转移规则时，蕴含了贪心思想：在叶子节点的父节点放置摄像头通常比在叶子节点放置更优。解题时，我们通过后序遍历实现DP，但决策点（何时放置摄像头）体现了贪心的局部最优选择。这种在DP框架内嵌入贪心决策点的模式，是解决复杂约束优化问题的常见手法。

面对这类混合题型，有效的解题训练应遵循以下路径：首先，尝试分析问题是否具有最优子结构和贪心选择性质。可以思考“如果每一步都选择某种局部最优，能否导向全局最优？”其次，若贪心策略无法被简单证明或存在反例，则需转向动态规划，但在定义状态和转移时，可借鉴贪心策略带来的排序或决策顺序优化。最后，在实现动态规划后，可再次审视是否存在用贪心思想简化状态转移或降低空间复杂度的可能。

总而言之，LeetCode中的贪心与动态规划混合题打破了算法策略的界限，它们要求解题者具备灵活的思维转换能力。掌握这类题目，意味着不仅能熟练套用模板，更能深刻理解问题本质，在贪心的高效与动态规划的周全之间找到最佳平衡点。这种能力的锤炼，对于应对实际开发中复杂的决策优化场景，无疑是一笔宝贵的财富。