ARTICLE · 978626
2026国防素养大赛无人机赛真题:指令纠错解析
无人机编队飞行前，教练手里的「标准指令序列」和选手程序生成的「实际指令序列」经常对不上：多按了一下、漏了一段、方向打反……怎么用算法快速算出最少要改几个字符才能让两者一致？这正是全国青少年国防素养大赛·智能无人系统应用赛中「程序指令纠错」类题目的核心。今天我们用一道原创真题，把编辑距离（动态规划）彻底讲透。
一、赛事背景：国防素养大赛 · 智能无人系统应用赛
全国青少年国防素养大赛是教育部 2025—2028 学年白名单赛事（序号 43，主办单位含南京理工大学），设「主题演讲、国防科技创意设计、国防技能挑战、智能无人系统应用」四大赛道。其中智能无人系统应用赛聚焦无人机实操与航空编程，是极具科技趣味的热门赛道，也是算法思维的绝佳练兵场。
二、原创真题：无人机编队指令纠错
【题意】给定标准指令序列 S 与选手实际指令序列 T，指令仅由 U(上) D(下) L(左) R(右) H(悬停) 组成。一次「编辑」可以是：删除一个字符、插入一个字符、或把某个字符替换成另一个（三种操作各计 1 次代价）。求把 T 变成 S 的最少编辑次数。
【输入】两行，分别为 S 与 T。【输出】一个整数，表示最小编辑次数。
【样例】
输入： UDLR ULR 输出： 1 输入： RRDDLL RDL 输出： 3 输入： HUDLR UDLRH 输出： 2
三、算法核心：编辑距离（动态规划）
设 dp[i][j] 表示「把 T 的前 i 个字符变成 S 的前 j 个字符」的最少代价。边界：空串变空串代价 0；空串变长度为 j 的串需插入 j 次，故 dp[0][j]=j；同理 dp[i][0]=i。转移时，看 T[i-1] 与 S[j-1] 是否相同：
若相同： dp[i][j] = dp[i-1][j-1]（直接匹配，无代价）；若不同，可从三种操作取最小：删除 T[i-1]（dp[i-1][j]+1）、插入S[j-1]（dp[i][j-1]+1）、替换（dp[i-1][j-1]+1）。
最终答案即 dp[n][m]，时间复杂度 O(n·m)，空间复杂度可用滚动数组压到 O(m)。
四、C++ 解法
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int minEdit(const string& a, const string& b) { int n = a.size(), m = b.size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); for (int i = 0; i <= n; i++) dp[i][0] = i; for (int j = 0; j <= m; j++) dp[0][j] = j; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { int cost = (a[i-1] == b[j-1]) ? 0 : 1; dp[i][j] = min({ dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost }); } return dp[n][m]; } int main() { string a, b; while (cin >> a >> b) cout << minEdit(a, b) << " "; return 0; }五、Python 解法
def min_edit(a: str, b: str) -> int: n, m = len(a), len(b) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(n + 1): dp[i][0] = i for j in range(m + 1): dp[0][j] = j for i in range(1, n + 1): for j in range(1, m + 1): cost = 0 if a[i - 1] == b[j - 1] else 1 dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost) return dp[n][m] if __name__ == "__main__": a = input().strip() b = input().strip() print(min_edit(a, b))
六、七考点拆解
- 状态定义
：把「前缀对前缀」的代价作为子问题，避免重复计算。 - 边界初始化
： dp[i][0]=i、dp[0][j]=j是递推的基石。 - 三种转移
：删除 / 插入 / 替换（或匹配）取最小。 - 匹配零代价
：相同字符时 cost=0，直接沿对角线继承。 - 答案位置
： dp[n][m]即整体最小代价。 - 空间优化
：只用上一行，滚动数组把空间降到 O(m)。 - 复杂度
：时间 O(n·m)，空间 O(n·m) 或 O(m)。
七、进阶挑战
- 带权编辑
：替换代价更高（如 2），只需改 cost 与取 min 的口径。 - 路径还原
：从 dp[n][m]逆推，输出一种最优操作序列（替换/删除/插入）。 - 仅允许删除+插入
：此时等价于 |a|+|b|-2·LCS，可改用最长公共子序列思路。
八、互动引导
把样例 2 的 S=RRDDLL、T=RDL 代入代码跑一遍，看看答案是不是 3？你还能想到哪些「指令纠错」的真实场景？欢迎在评论区晒出你的代码或思路，我们下期拆解「滚动数组」的空间压缩技巧！
📚 免费少儿编程资料（夸克网盘领取）
以下资料来自夸克网盘分享。个人号链接暂不支持直接点击，请长按或复制下方链接，打开夸克网盘 App / 网页粘贴即可保存：
1. 全国青少年信息素养大赛复赛集训题目Python&C++.docx https://pan.quark.cn/s/93995d3cb150 2. 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf https://pan.quark.cn/s/da97b5dbf75d 3. Python背记手册.pdf https://pan.quark.cn/s/7568ae9ca92b 4. Python课程 https://pan.quark.cn/s/a94bf02d00c6 5. 2024信息素养大赛图形化复赛集训题答案3-9 https://pan.quark.cn/s/6ccab7ec3cbc 6. 2025年03月份电子学会考级真题 https://pan.quark.cn/s/4403c4228912 7. 2025全国青少年信息素养大赛赛项说明 https://pan.quark.cn/s/d9d0df4a9f29 8. 青少儿信息素养大赛编程资料 https://pan.quark.cn/s/4ab6bd83be8a
资料持续更新，关注本号第一时间获取新分享。