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[i1] 可以由左手按也可以由右手按。如果由某根手指按那么它就要从当前位置移动到新字母的位置另一根手指不动。动态规划定义设dp[i][l][r]表示已经按完了前i个字母i 从 0 开始并且左手停在字母l0~25右手停在字母r时需要的最小移动总距离。初始时i0第一个字母可以用任意一根手指按另一根手指可以停在任意位置不花代价。所以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){intx1p/6,y1p%6;intx2q/6,y2q%6;returnabs(x1-x2)abs(y1-y2);}intminimumDistance(string word){// 动态规划intnword.size();intdp[n][26][26];// 输入第i个字母后左手的位置和右手的位置// 每个位置都初始化为最大值for(inti0;in;i){for(intj0;j26;j){fill(dp[i][j],dp[i][j]26,INT_MAX1);}}// 初始化两个手指的第一次for(inti0;i26;i){dp[0][i][word[0]-A]dp[0][word[0]-A][i]0;}// 遍历每一个字母for(inti1;in;i){// 上一轮和这一轮是同一只手intcurword[i]-A;// 当下要按的字母intprevword[i-1]-A;// 上一个按下的字母intdgetDistance(prev,cur);// 计算移动的距离for(intj0;j26;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(prevj){// 上一轮和这轮不是同一只手按的for(intk0;k26;k){intd0getDistance(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);}}}}intansINT_MAX1;for(inti0;i26;i){for(intj0;j26;j){ansmin(ans,dp[n-1][i][j]);}}returnans;}};复杂度分析复杂度量级时间复杂度O(n × 26²)空间复杂度O(n × 26²)总结这道题是一个典型的双指动态规划问题。我们通过记录两根手指的当前位置逐步转移状态。核心难点在于想清楚“两个手指可以交替按字母”并且要正确处理换手时的距离计算。我们可以利用dp[i][l][r]的对称性以及判断prev j来减少不必要的枚举。掌握这种 DP 后类似的“多指键盘输入最小移动距离”问题都可以用类似方法解决。