导弹拦截算法题详解：从DP到贪心与二分优化-育师

导弹拦截这个问题，在算法圈里算是老面孔了。它表面上是一道模拟题，实际考察的是最长上升子序列的变体和贪心策略的应用。很多初学者第一次做这道题，都会被“第一问求最长不上升子序列，第二问求最少系统数”这个组合搞晕——明明两个问题看起来差不多，解法却完全不同。这篇文章我打算把这道题的每一个细节都拆开揉碎，从暴力DP到二分优化，从“为什么贪心是对的”到“等号到底怎么处理”，一次性讲透。

这道题适合正在学动态规划和贪心的读者，也适合准备机试、笔试但总在LIS变体上卡壳的人。看完之后你不仅能AC这道经典题，还能把“最长上升子序列”这个知识点的底层逻辑真正吃透。

1. 题目理解与整体思路拆解

1.1 题意到底在说什么

先还原一下题目的原始场景：某套防御系统发射的拦截导弹，每一发炮弹都有一个最大飞行高度，而且这套系统有个硬性规定——炮弹拦截的高度必须严格递减，也就是说，第一发能打到10000米，第二发最多只能打9999米，不能反弹回去打更高的目标。

现在给出一串来袭导弹的高度序列，比如389 207 155 300 299 170 158 65，问两个问题：

一套系统最多能拦截多少枚导弹？
要拦截所有导弹，最少需要几套系统？

注意这两问的微妙之处。第一问是“在保证拦截顺序合法的情况下，最多能拦截几枚”，这本质上是在一个序列里找一段尽可能长的、单调不上升的子序列。第二问则变成了“如何用最少的递减序列把整个序列覆盖掉”，这是一个划分问题，不是子序列问题。

很多教程会把这两问都归到LIS上，但第二问其实更贴近贪心的“最小链覆盖”思想。把这两个问题放在一道题里，就是为了考察你能否区分“最长子序列”和“最少覆盖序列”这两个概念。如果混为一谈，第二问十有八九会写成“求最长上升子序列长度”然后直接输出，答案恰好在某些样例上也能过，但本质上是错的。

1.2 第一问的暴力DP为什么是O(n²)

第一问是经典的最长不上升子序列。定义dp[i]表示“以第i枚导弹结尾的最长不上升子序列长度”。为什么一定要强调“以第i个元素结尾”？因为子序列的连续性不是按位置来的，而是按逻辑关系来的。

转移的思路是：对于每个i，往前找所有高度不小于a[i]的j，只要a[j] >= a[i]，就意味着第i枚导弹可以接在第j枚导弹后面，形成合法的不上升关系。所以：

dp[i] = max(dp[j] + 1) 其中 j < i 且 a[j] >= a[i]

初始状态是dp[i] = 1，表示单独一枚导弹也能构成一个长度为1的序列。

这个做法的时间复杂度是 O(n²)，因为每个i都要扫描前面所有的j。当 n 在1000以内时完全没问题，但如果 n 到了100000，O(n²)就暴毙了。这也引出了后面的二分优化方案，后面我会专门讲。

1.3 第二问的贪心直觉

第二问如果按直觉来想，最简单的策略就是“能拦就拦”。每次来一枚新导弹，先在现有的拦截系统里找一套“高度够高、但又不会浪费”的系统来拦它。

这里的“不会浪费”四个字是关键。比如当前两套系统的最高可拦截高度分别是300和200，现在来了一枚250的导弹。用300的那套能拦，用200的那套拦不了。虽然两套都能用300那套来拦，但更好的策略是保留300那套，因为它以后还能拦更高的导弹。如果现在把300那套用了，之后来一枚280的导弹，就只能再开新系统，白白浪费。

所以第二问贪心的核心是：每次选择“当前可拦截高度大于等于目标高度，且是所有可用系统中可拦截高度最小”的那一套。如果所有系统都拦不了，才新建一套系统，新系统的高度上限就是这枚导弹的高度。

这个策略可以保证系统数量最少，后面我会结合“决策单调性”来解释它为什么是对的，而不是靠感觉。

2. 第一问深入：最长不上升子序列的DP推导

2.1 状态转移的完整推演

我们拿题目自带的示例序列来手跑一遍：

a = [389, 207, 155, 300, 299, 170, 158, 65]

初始化全部dp[i] = 1。

i=1，a[1]=389，前面没有元素，dp[1]=1
i=2，a[2]=207，往前找：389 >= 207，所以dp[2] = dp[1]+1 = 2
i=3，a[3]=155，往前找：389 >= 155，207 >= 155，分别算得2和3，取最大，dp[3] = 3
i=4，a[4]=300，往前找：389 >= 300，得到2；207 < 300，不能接；155 < 300，不能接。所以dp[4] = 2
i=5，a[5]=299，往前找：389 >= 299，得到2；207 < 299，不行；155 < 299，不行；300 >= 299，得到 dp[4]+1=3，所以dp[5] = 3
i=6，a[6]=170，往前找：389、207、300、299都 >= 170，其中dp[5]+1=4，dp[2]+1=3，dp[4]+1=3，最大的是4，所以dp[6] = 4
i=7，a[7]=158，往前找：dp[6]+1=5最大，所以dp[7] = 5
i=8，a[8]=65，往前找：dp[7]+1=6最大，所以dp[8] = 6

最终答案不是dp[n]自动等于6吗？恰好在这个例子里是。但如果导弹高度是递增的，比如1 2 3 4 5，算出来的dp[1]=1, dp[2]=1, ..., dp[5]=1，最大答案应该是1，但dp[n]也是1，碰巧一致。如果序列是5 1 2 3 4，答案应该是2（5 4或者5 3之类），但dp[4]是以4结尾的序列长度，算出来是2（5 4之间的dp值是2），还是碰巧。真正能暴露问题的是1 3 2这样的序列：答案应该是2，dp[2]=1（以3结尾的最长不上升是1），dp[3]=2（以2结尾可以接3），但如果你只输出dp[n]，会得到2，恰好对；再来一个3 1 2：答案应该是2（3 1或者3 2），dp[2]=2，dp[3]=2，还是对。

这里要特别提醒：很多题解会直接输出dp[n]，在大多数测试点能过，但逻辑上不严谨。正确答案应该取dp数组的最大值，而不是dp[n]。因为最长不上升子序列不一定结束在最后一个元素上。比如序列5 3 4 2 1，最长的是5 3 2 1，长度4，结束在最后一个元素；但如果序列是5 1 4 3 2，最长可以是5 4 3 2，结束在最后一个，也碰巧。真正反例是2 1 3，最长不上升是2 1或3，最长长度2，而dp[3]是以3结尾的序列长度，只有1。如果只看dp[n]就错了。

2.2 相等高度的处理：不上升 vs 严格下降

题目要求“每一发炮弹的高度不得高于前一发的高度”，也就是允许相等。这意味着转移条件是a[j] >= a[i]，而不是a[j] > a[i]。

这里是最容易踩坑的地方。如果写成a[j] > a[i]，你求的就是“最长严格递减子序列”，而题目要求的是“最长不上升子序列”，两者在高度重复出现时结果完全不同。

举例：5 5 5 5，最长不上升子序列是4，因为可以连续拦截4枚高度都为5的导弹。但如果写成严格递减，那答案就变成了1，瞬间WA。

所以记住这个口诀：题目说“不高于”，就是>=；题目说“低于”，才是>。同样思路也适用于最长上升子序列和最长严格上升子序列的区别。

2.3 代码实现与细节

第一问的O(n²)实现非常短：

#include <bits/stdc++.h> using namespace std; int main() { vector<int> a; int x; while (cin >> x) a.push_back(x); int n = a.size(); vector<int> dp(n, 1); int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a[j] >= a[i]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); } cout << ans << endl; return 0; }

几个细节提一下：

输入是不定长的，用while (cin >> x)或者getline切割都行。
初始化dp全为1，这个不能省。任何单个元素自己就是一个合法的子序列。
答案是ans全局最大值，不是dp[n-1]。

这个代码在 n <= 1000 的范围内性能足够，笔试机试基本都能过。但如果数据范围到了 10^5 甚至 10^6，就必须换二分优化了。

3. 第二问深入：贪心模拟拦截系统

3.1 贪心策略的完整描述

第二问常见的解法有两种：一种是“每来一枚导弹，在现有系统里找能拦住它的、且当前高度上限最小的系统”，另一种是“用数组模拟每个系统的当前高度，每次更新”。

我把第一种策略写成通俗的语言：

维护一个数组sys，sys[k]表示第 k 套系统当前能拦截的最高高度。
每来一枚高度为 h 的导弹：
- 遍历所有现有系统，找出满足sys[k] >= h的系统里，sys[k]最小的那个。
- 如果找到了，就把这个系统的sys[k]更新为h（因为拦截了这枚导弹后，这套系统的能力上限就降到了 h）。
- 如果没找到，说明所有系统都拦不了这枚导弹，就新开一套系统，把 h 加入sys数组。
最后sys的长度就是所需系统数。

为什么选择“能力上限最小且能拦住”的系统？因为我们要“节省火力”。用一个能拦300米高度的系统去拦100米的导弹，虽然能拦，但浪费了200米的余量。万一后面来一枚280米的导弹，本来300米系统可以拦，结果被100米的导弹消耗掉了，就只能新建系统。

3.2 手工推演示例

还是拿示例序列跑一遍：

389 207 155 300 299 170 158 65

来389：sys为空，新建，sys = [389]
来207：389 >= 207，更新389为207，sys = [207]
来155：207 >= 155，更新207为155，sys = [155]
来300：155 < 300，拦不了，新建，sys = [155, 300]
来299：155 < 299，但300 >= 299，且300是所有可用系统里高度最小的（另一个155不够格），更新300为299，sys = [155, 299]
来170：155 < 170，但299 >= 170，更新299为170，sys = [155, 170]
来158：155 < 158，但170 >= 158，更新170为158，sys = [155, 158]
来65：155 >= 65，更新155为65，sys = [65, 158]

最终需要2套系统。第一套拦截了389、207、155、65，第二套拦截了300、299、170、158。

这个结果很符合直觉：高度整体呈下降趋势时一套系统就能覆盖大部分，但300这个突然拔高的数值打断了一次连续性，所以需要第二套系统接住那一段相对较高的导弹。

3.3 贪心正确性的证明思路

第二问的贪心策略看起来显然，但要严格证明并不简单。这里提供一个比较直观的证明思路，不涉及复杂的数学工具。

假设我们当前有一组系统，编号1到m。每来一枚导弹h，按照策略，我们找到了第k号系统来拦截它，k满足是“所有能拦截系统里高度最小的”。

现在考虑任何其他合法策略，在这次决策时选择了一个不同的系统 k' 来拦截h。因为k是我们选的最小值，所以sys[k] <= sys[k']。更新后，k系统变为h，k'系统变为h，其他系统不变。

比较两种决策后的状态：我们的策略让第k号系统的高度变成了h，而其他策略让第k'号系统变成了h。我们的系统中，被“消耗”的是一个原本高度更小（或相等）的系统，也就是说，我们把高度更大的那个系统保留了下来。保留更高能力的系统，意味着以后面对更高的导弹时，我们有更多选择余地。所以我们的决策不会比任何其他决策更差。

不断重复这个归纳过程，贪心策略的最终系统数一定不大于任何其他策略的系统数，于是它就是最优解。

这个证明的核心就是“保留高能力资产”。在代码里，这个策略对应的是每次找一个>= h的最小值，也就是 lower_bound 的变体。

3.4 第二问代码实现

#include <bits/stdc++.h> using namespace std; int main() { vector<int> a; int x; while (cin >> x) a.push_back(x); vector<int> sys; for (int h : a) { bool ok = false; int best = -1; int bestIdx = -1; for (int i = 0; i < (int)sys.size(); i++) { if (sys[i] >= h) { if (bestIdx == -1 || sys[i] < best) { best = sys[i]; bestIdx = i; } } } if (bestIdx != -1) { sys[bestIdx] = h; } else { sys.push_back(h); } } cout << sys.size() << endl; return 0; }

这里有个容易犯的错误：很多初学者会写成“找到第一个大于等于h的系统就更新”，但如果你找到的是高度300的系统而不是高度155的系统（假设两者都能拦当前导弹），就可能造成浪费。必须强调“最小可用”三个字。

4. 从O(n²)到O(n log n)：二分优化全解析

4.1 为什么需要优化

当数据范围变大，n = 100000 甚至更大时，O(n²)的DP会超时。第一问和第二问都需要更高效的解法。

第一问的经典优化是“贪心 + 二分”，也就是维护一个数组d，d[i]表示“长度为 i 的不上升子序列的最后一个元素的最大值”。听起来有点绕，我们拆开说。

核心思想是：在构建子序列时，我们希望“末位元素尽可能大”，这样后面才有更多元素能接上去。比如当前已经有不上升子序列长度为2，可能存在多个长度为2的不上升子序列，它们的末位元素分别是30和50。显然50更好，因为后面要接一个比50更小的元素，比接在30后面更容易。

所以我们可以维护一个数组d，d[len]表示“所有长度为 len 的不上升子序列中，末位元素的最大值”。然后遍历导弹高度时，要么扩展新的长度，要么更新已有长度的末位值。

4.2 第一问的二分优化细节

处理不上升子序列时，d数组是单调不递增的还是单调递减的？我们来分析。

假设d[1] >= d[2] >= d[3]，这个性质必须成立。因为长度为2的不上升子序列的末位元素，必然不大于长度为1的不上升子序列的末位元素；否则长度为2的子序列就能和长度为1的子序列组合成更长的序列。这个性质可以通过归纳法严格证明。

遍历每个高度h时，我们要找的是“d中第一个小于 h 的位置”。为什么是“小于”而不是“小于等于”？因为不上升子序列允许相等。假设d = [50, 40, 30]，现在新来一个h = 40，它应该接在哪个长度后面？

长度为1的子序列末位是50，40 <= 50，可以接在后面，形成[50, 40]长度2。但d[2]已经是40，新形成的也是40，没变化。长度为2的子序列末位是40，40 <= 40，可以接，形成长度3。所以新来的40应该更新d[3]为40。这里d[3]原本是30，现在可以提升为40。

所以我们要找的是“d中第一个小于h的位置”，如果d中所有元素都不小于h，说明h可以接在最长子序列后面，扩展出一个新长度。

用 C++ 的upper_bound配合自定义比较器来实现，或者手写二分。这里的关键是明白upper_bound找的是“第一个大于h”的位置，而我们需要“第一个小于h”的位置，正好相反，所以要自定义比较规则。

一个更稳妥的写法是手写二分：

vector<int> d; d.push_back(a[0]); for (int i = 1; i < n; i++) { int h = a[i]; if (h <= d.back()) { d.push_back(h); } else { // 在d中找第一个小于h的位置，替换为h int l = 0, r = d.size() - 1; while (l < r) { int mid = (l + r) / 2; if (d[mid] < h) r = mid; else l = mid + 1; } d[l] = h; } } cout << d.size() << endl;

这里的d.size()就是最长不上升子序列长度。

4.3 第二问的二分优化

第二问的贪心策略里，我们需要在系统数组中找“第一个大于等于h的元素”，然后把它替换为h。如果没找到，就push_back。

系统数组sys是天然有序的吗？按贪心策略更新后，它始终保持递增吗？我们来看：每次把sys[k]更新为 h < sys[k]，数组还是有序的。每次新开系统加入 h，而h一定大于当前所有系统的值（因为所有系统都拦不了它），所以h会成为数组最大元素，加入后依然有序。

既然有序，就可以用二分查找定位替换位置。C++ 里直接用lower_bound找第一个>= h的元素即可：

vector<int> sys; for (int h : a) { auto it = lower_bound(sys.begin(), sys.end(), h); if (it != sys.end()) { *it = h; } else { sys.push_back(h); } } cout << sys.size() << endl;

这段代码极其简洁。lower_bound返回第一个不小于h的位置，直接替换，完美对应贪心的“最小可用系统”。

4.4 Dilworth定理：两问之间的桥梁

第二问还有一个很著名的结论：最少不上升子序列划分数等于最长上升子序列长度。

这就是Dilworth定理在序列上的特例。偏序关系定义为“i < j 且 a[i] >= a[j]”，那么最长链的长度就是不上升子序列最大长度，最小链覆盖数就是最长反链的长度，而最长反链就是最长上升子序列。

也就是说，第二问可以直接用求LIS的方法做：求一遍最长上升子序列（注意是严格上升，不是非降），输出长度即可。

这个发现让人非常爽，因为两问都可以用LIS的变体统一解决。代码上只需要把第一问的“不上升”改成“上升”，再跑一遍即可。

但要注意“上升”和“非降”的区别：第二问对应的是最长“严格上升”子序列，不是非降子序列。为什么？

直观的解释是：如果两个导弹高度相同，比如5 5，一套系统可以拦下两枚，意味着“高度相等”不算上升关系。那么关键的结论是：用最少的不上升序列覆盖一个序列，需要的数量等于最长严格上升子序列的长度。如果误写成非降子序列，5 5就会被算成长度为2的递增关系，答案变成2，而实际上1套系统就够。

所以再次强调：第一问是>=（不上升），第二问对应的是>（上升），两者在相等时刚好互补。写代码时一定要小心。

5. 常见问题与调试经验

5.1 输出dp[n]导致的隐蔽错误

这个问题我前面提过，但值得单独拿出来再说一遍。很多AC代码确实只是输出dp[n]，因为大部分测试数据里最长不上升子序列恰好结束在最后一个元素。但如果你用1 3 2这种用例测试，dp[2]（以3结尾）是1，dp[3]（以2结尾）是2，如果输出dp[n]恰好是2，还是对。

真正的反例需要让最长序列不结束在末尾。比如5 1 4 3 2，最长不上升子序列是5 4 3 2，结束在末尾，还是碰巧。那5 4 1 3 2 6呢？最长不上升是5 4 3 2，结束位置是倒数第二，dp[n]是1（以6结尾），如果用dp[n]就会WA。

所以写DP时，养成分开维护答案的习惯，别偷懒直接用dp[n]。

5.2 等号方向混淆

这是另一大坑。第一问遇到相等高度时，比如3 3，允许连续拦截，所以答案是2。如果写成a[j] > a[i]，打印出来的答案是1，瞬间WA。

第二问的Dilworth定理对应最长严格上升子序列，如果第二问误写成非降子序列，遇到3 3这种用例，会输出2，而正确答案是1（一套系统能拦下两枚高度相同的导弹）。

怎么记忆？可以用物理直觉：一套系统拦完一枚导弹后，上限降到这枚导弹的高度。如果下一枚导弹高度相同，它不高于当前上限，所以能拦。因此不上升序列允许相等。对应地，第二问需要的是“打破不上升覆盖的最少数量”，这个数量只有在严格上升时才增加，所以是严格上升子序列长度。

5.3 二分边界写错的排查

手写二分的题解里，最常见的bug是边界条件。比如第一问的二分，要小心l和r的初始值以及mid的取值方向。

一个建议：不要死记模板，把二分退化成“在有序数组中找到第一个满足条件的位置”，然后用左闭右开区间写：

int l = 0, r = d.size(); // 左闭右开 while (l < r) { int mid = (l + r) / 2; if (d[mid] < h) r = mid; else l = mid + 1; } d[l] = h; // 或者 d.insert(d.begin()+l, h)

这个写法更不容易出错。注意当l等于d.size()时，表示没有找到，需要push_back，而不是直接赋值。

5.4 关于二分优化的常见疑问

有读者会问：第一问的d数组能求出具体的子序列吗？很遗憾，不能直接用最终d数组还原出最长的那个子序列，因为d只记录了每个长度的最佳末位值，过程中可能丢失了中间元素的信息。

要还原具体子序列，需要额外维护一个pos数组，记录每个元素在DP过程中被安排到了哪个长度位置，然后从后往前回溯。这个复杂度虽然还是O(n log n)，但实现复杂度高不少。笔试面试一般只要求输出长度，所以还原子序列的需求不常见。但如果想深入理解，建议自己推一遍。

5.5 数据读取的问题

题目输入是“第一行是一枚导弹的高度，第二行是下一枚导弹的高度，以此类推，以文件结束符结束”。也就是说，可能是一行一个数，也可能是空格分隔的一行数。用while (cin >> x)是最稳妥的写法，不管什么格式都能正确读完。

有些初学者会用getline读整行然后 split，遇到多行的输入格式就会出错。直接用cin流读取是最省心的方案。

6. 题型扩展与进阶思考

6.1 拦截导弹变体

这道题有很多变体，万变不离其宗：

把“不上升”改成“严格下降”，第一问转移条件变成>，第二问对应最长非降子序列长度。
把“导弹高度”改成“导弹速度和高度双属性”，需要先按速度排序，再对高度做LIS，这就是经典的二维偏序问题。
如果允许“同时发射多枚拦截弹”，本质还是最少系统数问题，但每套系统的能力不再是固定的，而是可以动态调整，这就要用上贪心的“最小可用系统”思想。

6.2 从这题延伸出去的LIS全家桶

最长上升子序列问题本身变种极多：

最长不降子序列：转移条件a[j] <= a[i]，第二问对应最长严格递减子序列长度。
最长递减子序列：把数组翻转后求最长递增即可。
带权LIS：每个元素有值和权重，求权重和最大的递增子序列，这个需要树状数组优化。
循环数组LIS：数组可以循环移位，求所有可能起点下的LIS最大值，这个通常需要把数组复制一倍再处理。

理解了拦截导弹这道题，等于把LIS系列的核心套路都过了一遍。

6.3 贪心与DP的分工

最后聊聊一个更宏观的问题：什么时候用贪心，什么时候用DP？

这道题提供了一个很好的对比样本。第一问求的是“全局最优子序列长度”，这是一个典型的DP问题，因为状态之间存在依赖关系，需要记录从任意位置开始到当前位置的最优值。第二问求的是“最少系统数”，这个看上去也像DP，但贪心恰好能够解决，因为每次决策只需要考虑“当前哪套系统最合适”，而不用考虑未来，因为“保留更高上限系统”的策略具有局部最优性。

判断的标准是：如果一个决策的最优性可以从当前状态直接推导出来，不依赖未来信息，那贪心往往可行；如果当前决策会影响未来很多步的选择，那可能就是DP的范畴。LIS问题里“贪心+二分”的优化本质上是用贪心维护了DP的更新，这是更高级的用法，值得反复琢磨。

6.4 机试实战中的时间分配

如果你正在准备机试，我的建议是：看到这类经典题，先静下来把两问的含义理清楚，别急着写代码。用样例手推两遍，确认第一问的DP转移和第二问的贪心策略，然后再动手。

机试中时间复杂度往往比空间复杂度更容易卡人。n在1000以内时O(n²)完全够用，n到1e5就必须用O(n log n)的解法。如果对二分不熟，建议先把暴力写出来，保证能过一部分测试点，再优化。

还有一种常见情况是，题目没有告诉你n的范围，这个时候“能优化就优化”是最稳妥的策略。LIS的二分优化代码量很少，背下来绝对不亏。

写在最后

这道拦截导弹，我前前后后教过很多人，也见过无数种写法。有时候同一个代码，换一批测试数据，某些错误的写法就暴露了。所以每次我都强调：不要背题解，一定要亲手推一遍状态转移，亲手试几个反例。

我个人觉得，这道题最宝贵的地方在于，它把“DP求最优子序列”和“贪心求最小覆盖”这两个看似不同、实则互补的思想放在了同一道题里。想清楚“为什么第一问不能用贪心直接求”“为什么第二问不用DP也能做”，比AC这道题本身更重要。

如果你现在看完这篇文章，能自己推导出第二问的lower_bound更新过程，并且能解释清楚为什么Dilworth定理在这里成立，那说明你是真的吃透了。以后再遇到LIS的变种题，心里会踏实很多。

导弹拦截算法题详解：从DP到贪心与二分优化