LeetCode1320.最小移动距离的双指键盘输入问题

### 问题描述

在一个XY平面上，有一个定制的键盘布局，如图所示。每个大写英文字母位于特定的坐标处，例如字母A位于(0,0)，字母B位于(0,1)，字母P位于(2,3)，字母Z位于(4,1)。

给定一个待输入的字符串`word`，你需要计算并返回在仅使用两根手指的情况下，键入该字符串所需的最小移动总距离。坐标(x1,y1)和(x2,y2)之间的曼哈顿距离是|x1 - x2| + |y1 - y2|。

注意：两根手指的起始位置是零代价的，不计入移动总距离。手指可以任意选择从哪个字母开始。

#### 示例

```cpp
示例 1:
输入: word = "CAKE"
输出: 3
解释:
手指1从C到A的距离为2，手指2从K到E的距离为1，总距离为3。

示例 2:
输入: word = "HAPPY"
输出: 6
解释:
手指1从H到A再到Y的距离为6，手指2从P到P的距离为0。

示例 3:
输入: word = "NEW"
输出: 3

示例 4:
输入: word = "YEAR"
输出: 7
```

#### 提示
- 2 <= word.length <= 300
- 每个字符都是大写英文字母。

### 解题思路

我们使用动态规划来解决这个问题。定义`dp[i][c1][c2]`表示输入完第i个字符后，手指1在字符c1，手指2在字符c2时的最小移动距离。其中，0表示还没有输入字符，1-26表示A-Z。

初始化时，我们将第一个字符分配给手指1，并设置初始状态为0。接下来，我们遍历剩余字符，更新状态转移方程以计算最小移动距离。

#### 代码实现

```cpp
class Solution {
public:
int minimumDistance(string s) {
vector> pos(27, vector(2));
int count = 1;
for (int i = 0; i <5 && count <27; ++i)
for (int j = 0; j <6 && count <27; ++j)
pos[count++] = {i, j}; // 字符的坐标

int n = s.size(), mindis = INT_MAX;
int dp[301][27][27];
memset(dp, 0x7f, sizeof(dp));
dp[0][s[0] - 'A' + 1][0] = 0; // 输入第一个字符给手指1

for (int i = 1; i int c = s[i] - 'A' + 1; // 当前字符序号 1-26
for (int c1 = 1; c1 <= 26; ++c1) {
for (int c2 = 0; c2 <= 26; ++c2) {
if (dp[i-1][c1][c2] == 0x7f7f7f7f) continue; // 状态不存在

// 当前字母c由第1个手指输入
dp[i][c][c2] = min(dp[i][c][c2], dp[i-1][c1][c2] + abs(pos[c][0] - pos[c1][0]) + abs(pos[c][1] - pos[c1][1]));

// 当前字母c由第2个手指输入
if (c2 == 0) // 第二个手指还没输入
dp[i][c1][c] = min(dp[i][c1][c], dp[i-1][c1][c2]); // 第一次输入没有成本
else
dp[i][c1][c] = min(dp[i][c1][c], dp[i-1][c1][c2] + abs(pos[c][0] - pos[c2][0]) + abs(pos[c][1] - pos[c2][1]));
}
}
}

for (int c1 = 1; c1 <= 26; ++c1)
for (int c2 = 0; c2 <= 26; ++c2)
mindis = min(mindis, dp[n-1][c1][c2]);

return mindis;
}
};
```

### 性能分析

上述代码的时间复杂度为O(n * 26^2)，空间复杂度为O(n * 26^2)，其中n是字符串长度。实际运行时间为32ms，内存消耗为7.5MB。

更多内容请关注我的博客和公众号，一起学习进步！