leetcode热题 - 3

二指输入的最小距离

问题描述

二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。
例如字母 A 位于坐标 (0,0)，字母 B 位于坐标 (0,1)，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。
给你一个待输入字符串 word，请你计算并返回在仅使用两根手指的情况下，键入该字符串需要的最小移动总距离。
坐标 (x1,y1) 和 (x2,y2) 之间的 距离 是 |x1 - x2| + |y1 - y2|。
注意，两根手指的起始位置是零代价的，不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。
（真题链接：二指输入的最小距离）

解题思路

我们可以把问题简化一下：键盘上的 26 个大写字母按行排列（每行 6 个，最后一行只有 Z 一个，但坐标依旧按 6 列计算），每个字母对应一个坐标。两根手指可以任意移动，起始位置任意且不花代价。我们需要按顺序打出 word 中的所有字母，每次只能用一根手指去按当前字母，问两根手指移动的总距离最小是多少。
关键观察
两根手指是独立的，某一时刻一根手指在某个字母上，另一根在另一个字母上（也可以相同位置）。
按完第 i 个字母后，我们只需要知道两根手指分别停在哪个字母上，以及此时已花的最小总距离。
下一个字母 word[i+1] 可以由左手按，也可以由右手按。如果由某根手指按，那么它就要从当前位置移动到新字母的位置，另一根手指不动。
动态规划定义
设dp[i][l][r]表示：已经按完了前i个字母（i 从 0 开始），并且左手停在字母l（0~25），右手停在字母r时，需要的最小移动总距离。
初始时（i=0），第一个字母可以用任意一根手指按，另一根手指可以停在任意位置（不花代价）。所以：

dp[0][word[0]][任意] = 0 dp[0][任意][word[0]] = 0

其余状态为无穷大。
状态转移
当我们要按第 i 个字母（当前字母cur = word[i]）时，可以从i-1的状态转移过来。
如果上一轮是左手按的prev = word[i-1]，那么这一轮可以：
左手继续按：左手从prev移动到cur，右手保持不动（位置 j）。
增加距离dist(prev, cur)，更新dp[i][cur][j]。
换成右手按：那么上一轮右手的位置必须是prev（因为上一轮左手按了prev，右手在某个k）。
现在右手从 prev 移动到 cur，左手保持不动（位置k）。
增加距离dist(prev, cur)，更新dp[i][k][cur]。
如果上一轮是右手按的 prev，对称处理。
还有一种情况：上一轮两根手指中有一根停留在prev上，另一根在别处，而这一轮用另一根手指按cur（即换手操作）。
代码中用if (prev ==j)来检查：如果上一轮右手位置 j 恰好等于上一个字母prev，说明上一轮是右手按的prev，那么这一轮我们可以用左手按cur，左手可以从任意位置k移动到cur，右手不动（仍然在 j）。
同理，如果prev == j也可以推出右手按的情况。

实际上更简洁的转移是：对于每个dp[i-1][l][r]，当前字母cur可以由左手按（l -> cur）或右手按（r -> cur）。代码中为了优化常数，只枚举了上一轮参与按字母的那根手指的位置，另一根手指位置任意，并通过prev == j判断来减少枚举量。
最终答案
处理完所有字母后，取dp[n-1][l][r]中的最小值即可。

代码实现

classSolution{public:intgetDistance(intp,intq){intx1=p/6,y1=p%6;intx2=q/6,y2=q%6;returnabs(x1-x2)+abs(y1-y2);}intminimumDistance(string word){// 动态规划intn=word.size();intdp[n][26][26];// 输入第i个字母后，左手的位置和右手的位置// 每个位置都初始化为最大值for(inti=0;i<n;++i){for(intj=0;j<26;++j){fill(dp[i][j],dp[i][j]+26,INT_MAX>>1);}}// 初始化两个手指的第一次for(inti=0;i<26;++i){dp[0][i][word[0]-'A']=dp[0][word[0]-'A'][i]=0;}// 遍历每一个字母for(inti=1;i<n;++i){// 上一轮和这一轮是同一只手intcur=word[i]-'A';// 当下要按的字母intprev=word[i-1]-'A';// 上一个按下的字母intd=getDistance(prev,cur);// 计算移动的距离for(intj=0;j<26;++j){dp[i][cur][j]=min(dp[i][cur][j],dp[i-1][prev][j]+d);// 左手从 prev 移到 cur，右手保持在 jdp[i][j][cur]=min(dp[i][j][cur],dp[i-1][j][prev]+d);// 右手从 prev 移到 cur，左手保持在 jif(prev==j){// 上一轮和这轮不是同一只手按的for(intk=0;k<26;++k){intd0=getDistance(k,cur);dp[i][cur][j]=min(dp[i][cur][j],dp[i-1][k][j]+d0);dp[i][j][cur]=min(dp[i][j][cur],dp[i-1][j][k]+d0);}}}}intans=INT_MAX>>1;for(inti=0;i<26;++i){for(intj=0;j<26;++j){ans=min(ans,dp[n-1][i][j]);}}returnans;}};

复杂度分析

总结

这道题是一个典型的双指动态规划问题。我们通过记录两根手指的当前位置，逐步转移状态。核心难点在于想清楚“两个手指可以交替按字母”，并且要正确处理换手时的距离计算。
我们可以利用dp[i][l][r]的对称性，以及判断prev == j来减少不必要的枚举。
掌握这种 DP 后，类似的“多指键盘输入最小移动距离”问题都可以用类似方法解决。