谁能帮我解决这个问题？
我们有一个来自某些特定 aplhabet 的 MxN 字符网格，例如 S={A,B,C,D}。
光标位于 (1,1) 位置，我们可以使用箭头键移动光标， 向上 ， 向下 ， 向左 ， 向右 ，和 选择字符(就像选择字符一样)在旧游戏中选择尼克)。给定来自 aplhabet S 的一些输入字符串，在它们权重相同的情况下，操作的最低成本是多少(例如，向右移动与选择字符的成本相同)？矩阵中也可以多次出现相同的字符。
例子:
字母 S={A,B,C,D}
矩阵 :ABDCCADBABAA
和输入字符串ADCABDA。
我不完整的解决方案是:
构建有向网格图并找到从 1,1 到结束字符的最短路径，中间字符类似于 TSP 中的城镇，并使用动态规划从最优子路径构建最优最终路径。问题是您可能以许多可能的结束字符结尾，而我完全不知道如何从较小的最佳子路径构建更长的最佳路径。
最佳答案
你应该用这样的节点构建一个图:
A1 A1 A1
A2 D1 C1 A2 B1 D1 A2
开始 A3 D2 C2 A3 B2 D2 A3 结束
A4 A4 B3 A4
A5 A5 A5
其中有边将一列中的每个节点连接到下一列中的每个节点。 Start 是 (1,1) 并且 End 无处不在。边权重是每对 key 之间的“出租车”距离。
现在这是一个相当简单的动态规划问题。您可以从任一端开始；从 Start 开始可能在概念上更简单。跟踪到目前为止到达每个节点的最低成本。
关于math - 最短键盘距离打字，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29594025/