计数器问题最优解详解

前几天在专栏里看到一个有意思的问题：https://www.bilibili.com/read/cv682026

这个问题的最优解是5次，当然我是借助计算机来求解的。

首先这个问题可以化简成和数字无关的问题。我们把0到9看成一个环（不是抽象代数里的环），即0<1<2<3<4<5<6<7<8<9<0<1<……，并且以第1位数字为基准，可以分别得到4个数字的大小次序，这里就用字母次序来表示大小次序。例如数字“1044”，因为1<4<0，可以表示成“ACBB”；数字“2018”，2<8<0<1，表示成“ACDB”。很容易发现，开头字母永远是A，因为我们是以第1位数字为基准。

对于1个4位数，转换后得到的字母，称为类型。

对于2个4位数，转换后得到相同字母的，我们称它们为同类。

在0000~9999这1万个数字中，一共有26种类型，分别是：

ABCD ABDC ACBD ACDB ADBC ADCB

AABC AACB ABAC ACAB ABCA ACBA ABBC ABCB ACBB ABCC ACBC ACCB

AABB ABBA ABAB AAAB

AABA ABAA ABBB

AAAA

为什么表示成类型？因为对于同类，很容易就能找到0代价（不按按钮）的互转方法，相当于把10000种可能化简到26种可能。

先看转轮，如果只转一格，那么对于所有类型可能的结果是：

上面的结果排除了转到自身类型的情况（已经知道同类之间可以互转，没有讨论的意义）。

只转一格的话，可能会把当前字母转成下一个字母。例如ABAC，转动A，A可能会变成B，但绝不可能变成C，如果A要到达C，必定会经过B。特殊的：C可能会变成A，因为C到A中间没有其他数字。ABAC转动A变成B后，就变成了BBBC，但是我们不会这样写，还要将它标准化成AAAB，即ABAC→AAAB。根据这些规则，我们可以枚举转轮对类型的全部变换结果。

再看按钮，可以先将1万个数字都转成类型，并且将数字自增1的结果也转成类型，这样我们就得到了所有类型按了按钮后的结果。如果结果可以用转轮得到的话，或者结果是自身，那么排除这个结果。结合上面转轮的结果，来个总的输出：

有了这个转换关系后，可以看出其实这就是个图，而且是最短路径问题。起点是AAAA(0000)，终点是ACDB(2018)，可以用Dijkstra算法之类的求出最短路径，结果是5，路径：AAAA * AAAB * AABC AABB * ABCC * ABCA * ACDB（*表示按了按钮）。

画张图表示的话就是这样：