用最少的动作打开一个锁

Question

考虑一个由车轮系统制成的锁.每个轮子按顺序有26个字母,每个轮子都用'a'.如果向上移动一个轮子,该轮子的显示将移动到字母表的下一个字母; 另一方面,向下移动一个轮,将显示切换到字母表的前一个字母.例如:

['a'] ->  UP  -> ['b']
['b'] -> DOWN -> ['a']
...
['z'] ->  UP  -> ['a']
['a'] -> DOWN -> ['z']

只需轻弹就可以将同一方向的轮子的任何连续子序列移动.这与以单一运动方式移动子序列的所有轮子具有相同的效果.例如,如果目标串是'zzzzzzzzz',单一的运动,改变'a'到'z',将车轮的整个序列改变从'a'给'z',从而到达目标串-打开锁.

如何确定打开锁的最小移动次数？这个问题有动态解决方案吗？该算法必须产生以下结果:

           Target string         | # moves
   ______________________________ __________
1 | abcxyz                       |    5
2 | abcdefghijklmnopqrstuvwxyz   |   25
3 | aaaaaaaaa                    |    0
4 | zzzzzzzzz                    |    1
5 | zzzzbzzzz                    |    3

案例1,目标abcxyz:

aaa[aaa] -> DOWN -> aaazzz
aaa[zz]z -> DOWN -> aaayyz
aaa[y]yz -> DOWN -> aaaxyz
a[aa]xyz ->  UP  -> abbxyz
ab[b]xyz ->  UP  -> abcxyz

案例5,目标zzzzbzzzz:

[aaaaaaaaa] -> DOWN -> zzzzzzzzz
zzzz[z]zzzz ->  UP  -> zzzzazzzz
zzzz[a]zzzz ->  UP  -> zzzzbzzzz

Answer 1

这个问题可以重述为：

将字符串 S 变成仅包含“a”的字符串的最小移动次数是多少？

定义：

将连续子序列视为字符串中相等字符的序列。最小的连续子序列自然是单个字符。如果对小子序列进行标准化，自然会得到更大的子序列，最终达到单个子序列——整个字符串。

标准化为什么：

角色只能向上或向下移动，因此，角色本身就是一系列向上和向下移动。字符表示的最坏情况是字母表中间的字母，这至少需要len(alphabet) / 2描述移动。在字母表中{a..z}，最坏的情况是'm'和'n'。

由于我们想要最小化移动次数，因此我们需要向下拉字母C <= m，然后向上拉字母C >= n。因此，为了最小化标准化过程，我们必须找到需要相同标准化动作的最大子序列。例如，如果我们有一个目标zzzzbzzzz，我们知道最小方向是UUUUDUUUU——U 代表向上，D 代表向下。

正火：

对于每次移动，计数器都会递增，从而产生转换字符串所需的最少移动次数。考虑到上面的例子，我们可以采取以下步骤：

# = 0 | zzzzbzzzz | UUUUDUUUU  (choose the smallest subsequence to normalize)
# = 1 | zzzzazzzz | UUUUDUUUU  (since 'a' is the base character, we choose
                              the move that increases the largest subsequence;
                              if 'a' was the first or last character,
                              moving it would simply be overhead)
# = 2 | zzzzzzzzz | UUUUUUUUU  (choose the subsequence to normalize)
# = 3 | aaaaaaaaa | _________  (choose the subsequence to normalize)

另一个例子，使用目标字符串abcxyz：

# = 0 | abcxyz | _DDUUU  (choose the smallest subsequence to normalize)
# = 1 | aabxyz | __DUUU  (choose the smallest subsequence to normalize)
# = 2 | aaaxyz | ___UUU  (choose the smallest subsequence to normalize)
# = 3 | aaayza | ___UU_  (choose the smallest subsequence to normalize)
# = 4 | aaazaa | ___U__  (choose the smallest subsequence to normalize)
# = 5 | aaaaaa | ______  (choose the smallest subsequence to normalize)

编辑：

正如@user1884905 所指出的，所提出的这个解决方案并不是最佳的。对于目标字符串mn，该算法不会得出最优解：

# = 0  | mn | DU  (choose the smallest subsequence to normalize)
# = 1  | ln | DU  (choose the smallest subsequence to normalize)
# = 2  | kn | DU  (choose the smallest subsequence to normalize)
...
# = 12 | an | _U  (choose the smallest subsequence to normalize)
# = 13 | ao | _U  (choose the smallest subsequence to normalize)
# = 14 | ap | _U  (choose the smallest subsequence to normalize)
...
# = 24 | aa | __  (choose the smallest subsequence to normalize)

这并不是最佳的，因为以下步骤需要较少的移动：

#0    #1    #2    ...    #12
mn -> mm -> ll -> ... -> aa

也许贪心算法的最佳子结构在于减少字符与字符串之间的全局距离，而不是关注这些字符与基本情况（'a'）之间的差异。