DP与贪心的‘梦幻联动’：一道AcWing 1010拦截导弹题，我悟了两种算法思想

DP与贪心的协同作战：从拦截导弹问题看算法思想的融合

导弹拦截问题就像一场精心设计的算法交响乐，其中动态规划和贪心算法各自演奏着独特的旋律，却又和谐共鸣。当我第一次在AcWing 1010题遇到这个问题时，那种"原来如此"的顿悟感至今难忘——看似独立的两个子问题，竟然完美展现了两种经典算法思想的精髓与互补性。

1. 问题本质与算法选择

导弹拦截问题包含两个看似简单却暗藏玄机的子问题：计算单系统最多拦截导弹数（最长非上升子序列）和计算拦截全部导弹所需最少系统数（最长上升子序列）。这两个问题就像一枚硬币的两面，分别对应着动态规划和贪心算法的典型应用场景。

**为什么第一个问题适合DP而第二个适合贪心？**关键在于问题特性：

• 最长非上升子序列具有重叠子问题特性：每个导弹能否被拦截取决于前面导弹的状态，需要记录中间结果
• 最少系统数问题具有贪心选择性：可以通过维护当前各系统的最低拦截高度来做出局部最优选择

实际工程中，这种算法组合应用非常普遍。比如网络流量控制可能同时需要DP进行资源分配和贪心进行优先级调度。

2. 动态规划解法：最长非上升子序列

标准的O(n²)动态规划解法是算法初学者的必修课。我们需要定义f[i]表示以第i个导弹结尾的最长非上升子序列长度：

def max_intercepted_missiles(heights): n = len(heights) dp = [1] * n for i in range(1, n): for j in range(i): if heights[i] <= heights[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)

这个解法虽然直观，但存在明显的优化空间。通过观察状态转移方程，我们可以发现：

1. 决策单调性：当h[i] ≤ h[j]时，f[i]可能从f[j]转移而来
2. 冗余计算：内层循环存在大量重复比较

3. 贪心解法：最少拦截系统数

第二个问题的解法展现了贪心算法的精妙之处。我们需要维护一个数组记录各系统当前能拦截的最低高度：

def min_interception_systems(heights): systems = [] for h in heights: pos = bisect.bisect_right(systems, -h, lo=0, hi=len(systems)) if pos == len(systems): systems.append(-h) else: systems[pos] = -h return len(systems)

这个解法之所以能达到O(n log n)复杂度，关键在于：

• 利用二分查找确定导弹应该加入哪个系统序列
• 维护的systems数组始终保持有序性
• 通过取负数将问题转化为寻找最长上升子序列

贪心选择的正确性证明：

1. 每次选择能拦截当前导弹的最小高度系统（通过二分查找实现）
2. 这样可以为后续更高的导弹保留更大的拦截空间
3. 最终systems数组的长度就是所需的最少系统数

4. 算法优化与进阶思考

理解了基础解法后，我们可以进一步探索优化空间和算法间的深层联系：

DP优化思路：

• 使用二分查找优化内层循环
• 结合树状数组或线段树加速区间查询
• 考虑空间复杂度的优化

贪心算法的本质：

• 实际上是在求解Dilworth定理中的链划分问题
• 最少系统数等于导弹高度序列的最长上升子序列长度
• 这种对偶关系在组合数学中很常见

两种解法的对比：

5. 实战技巧与常见误区

在实际编码实现时，有几个容易踩坑的地方值得特别注意：

DP实现的陷阱：

• 初始条件设置不当（每个导弹至少能拦截自己）
• 状态转移条件写反（注意是≤而不是≥）
• 结果取max的位置错误

贪心实现的技巧：

• 使用bisect模块简化二分查找实现
• 处理负数技巧避免重复造轮子
• 边界条件处理（空输入等情况）

一个常见的错误实现：

# 错误示例：直接寻找最长上升子序列 def wrong_min_systems(heights): lis = [] for h in heights: pos = bisect.bisect_left(lis, h) if pos == len(lis): lis.append(h) else: lis[pos] = h return len(lis) # 这实际上计算的是最长上升子序列长度

正确的做法应该是在第一个问题中计算最长非上升子序列，在第二个问题中计算最长上升子序列——这种对称性正是题目设计的精妙之处。

6. 算法思想的延伸应用

理解了这两种算法在导弹拦截问题中的应用后，我们可以将其思想迁移到其他场景：

DP思想的应用场景：

• 股票买卖问题（最大收益计算）
• 字符串编辑距离
• 背包问题及其变种

贪心思想的应用场景：

• 任务调度问题
• 霍夫曼编码
• 区间覆盖问题

特别有趣的是，有些问题可以同时用两种算法解决但效率不同。比如硬币找零问题：

• DP解法可以保证得到最优解
• 贪心解法在特定面额下也能得到最优解但通常更快

7. 从题目到思维的提升

真正掌握这道题的精华不在于记住代码，而在于培养三种关键能力：

1. 问题分解能力：将复杂问题拆解为可解决的子问题
2. 算法选择直觉：根据问题特征快速匹配适合的算法范式
3. 优化思维：从不最优的解法出发，逐步思考改进空间

我在多次刷题后发现，很多难题都是基础算法的组合变形。就像这道题，表面是两道题，实则是动态规划和贪心算法的完美配合演出。