礼拜一-礼拜五:09.00 早上-06.00 下午

公司新闻

指令串最少改几个按键才能变成目标序列:规则练习第24例

2026-11-09

练习输入序列时,可以把遗漏、误按和多按分别理解为插入、替换和删除。最少操作数提供一种明确的差异度,但它与简单统计不同位置的字符数并不一样。

每次插入、删除或替换一个符号成本都为一,相同符号保留成本为零。表格横轴为目标前缀、纵轴为原序列前缀;每个格子比较左边加一、上边加一以及左上角加本次匹配成本。

本例输入与约定

原序列CDADACB,目标序列CBBCCBCB;符号仅为抽象按键编号。

完整计算记录

目标前缀列:空串,C,CB,CBB,CBBC,CBBCC,CBBCCB,CBBCCBC,CBBCCBCB 空串 | [0, 1, 2, 3, 4, 5, 6, 7, 8] C | [1, 0, 1, 2, 3, 4, 5, 6, 7] CD | [2, 1, 1, 2, 3, 4, 5, 6, 7] CDA | [3, 2, 2, 2, 3, 4, 5, 6, 7] CDAD | [4, 3, 3, 3, 3, 4, 5, 6, 7] CDADA | [5, 4, 4, 4, 4, 4, 5, 6, 7] CDADAC | [6, 5, 5, 5, 4, 4, 5, 5, 6] CDADACB | [7, 6, 5, 5, 5, 5, 4, 5, 5] 最少修改数:5。

表中编号仅用于识别本例的元素。读取一个结果时,应先核对它对应的输入、处理顺序和边界约定;布尔值表示条件是否成立,空集合表示没有符合要求的对象,不应把这些字段混成同一种数值。

复核方法与适用范围

空串到长度n的串需要n次插入,反向需要n次删除。最终数值位于两个完整前缀相交处,不能把整张表的数值相加;插入和删除会改变后续位置的对应关系。

这只是字符串编辑距离,不表示玩家实际反应时间或动作难度。若游戏允许一次交换相邻按键,或不同错误有不同成本,应修改操作集合和规则,不能继续套用本例的单位成本表。

练习时可以先独立计算最前面的一步,再检查最后的整体不变量。若结论不同,应保留各步记录,定位第一处差异;只调整最终数字会掩盖规则理解上的问题。改变输入后也要重新演算,而不是照抄这一例的输出。