问题链接英文题库题目描述二指输入法自定义键盘在XY平面上的布局如图上图。其中每个大写英文字母都位于某个坐标，比如字母A在坐标(0,0)，字母B在坐标(0,1)，字母P在坐标(2,3)，字母Z在坐标(4,1)处。给定一个待输入的字符串单词，请计算并返回仅用两根手指键入该字符串所需的最小总距离。坐标(x1,y1)和(x2,y2)之间的距离为|x1-x2|+|y1-y2|。请注意，两个手指的初始位置是零成本的，不计入移动的总距离。两根手指的起始位置不必从第一个字母或前两个字母开始。示例1：输入：word="CAKE"输出：3解释：使用两个手指输入“CAKE”的最佳方法之一是：字母“C”上的手指1->移动距离=0手指1在字母“A”上打开->移动距离=从字母“C”到字母“A”的距离=2手指2在字母“K”上->移动距离=0手指2在字母“E”上->移动距离=从字母“K”的距离'到字母'E'=1总距离=3示例2：输入：word="HAPPY"输出：6解释：用两根手指输入“HAPPY”的最佳方法之一是：手指1在字母'H'上->移动距离=字母“A”上的手指1->移动距离=从字母“H”到字母“A”的距离=字母“P”上的手指2->移动距离=字母“P”上的手指2->行程距离=从字母“P”到字母“P”的距离=0手指1在字母“Y”上->行程距离=从字母“A”到字母“Y”的距离=4总距离=6示例3：输入：word="NEW"输出：3示例4：输入：word="YEAR"输出：7提示：2<=word.length<=300每个word[i]都是一个大写的英文字母。我没有想出自己解决问题的想法。我在比赛排行榜第一页学会了随变法会的代码。这段代码是我看懂后自己写的。结果和原来的代码一样。准备定义一个字母位置表，然后定义一个函数find_distance，求任意两个字母之间的距离。mapx[f1,f2]=setpmapx是一个字典，f1表示当前状态下第一根手指的位置，f2是第二根手指的位置，None表示手指还没有被使用过，setp是现在移动的总距离.初始状态mapx[单词首字母，None]=0表示我用第一只手打第一个字母，第二只手没有动，一共动了0步。状态转移方程从单词的第二个字母开始遍历单词，对于每个字母，检查**上一步**的所有状态（因为只需要上一步，所以不需要dp数组，直接覆盖上次的结果即可everytime)对于每个状态，尝试用第一根手指敲击当前字母，用第二根手指敲击当前字母，最后返回地图中的最小值。欢迎来到我的博客看看我刷过的其他题目：刷题代码类解法：defminimumDistance(self,word:str)->int:iflen(word)==2:#如果只有两个字母，不需要移动return0#字母位置表pos={}ch=ord('A')foriinrange(5):forjinrange(6):pos[chr(ch)]=(i,j)ifch==ord('Z'):breakch+=1#print(pos)#{'A':(0,0),'B':(0,1),'C':(0,2),'D':(0,3),'E':(0,4),'F':(0,5),'G':(1,0),'H':(1,1),'I':(1,2),'J':(1,3),'K':(1,4),'L':(1,5),'M':(2,0),'N':(2,1),'O':(2,2),'P':(2,3),'Q':(2,4),'R':(2,5),'S':(3,0),'T':(3,1),'U':(3,2),'V':(3,3),'W':(3,4),'X':(3,5),'Y':(4,0),'Z':(4,1)}deffind_distance(a,b):#求两个字母a和b之间的距离如果a==None：返回0返回abs(pos[a][0]-pos[b][0])+abs(pos[a][1]-pos[b][1])mapx={}mapx[(word[0],None)]=0#map[(a,b)]=setp表示当前第一根手指在a上，第二根手指在b上，步数为setp#None表示这个手指还没有被word[1中的cur使用过:]:next_map={}forfinger1,finger2inmapx:f1_dis=find_distance(finger1,cur)#手指1到当前字母的距离f2_dis=find_distance(finger2,cur)#手指2到当前字母的距离new_state1=(cur,finger2)#食指按下当前字母（当然食指状态不变）new_state2=(finger1,cur)#食指按下当前字母fornew_state,disin((new_state1,f1_dis),(new_state2,f2_dis)):如果next_map中有new_state:next_map[new_state]=min(mapx[(finger1,finger2)]+dis,next_map[new_state])else:next_map[new_state]=mapx[(finger1,finger2)]+dismapx=next_mapreturnmin(mapx.values())
