考虑一个由车轮系统制成的锁.每个轮子按顺序有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 …