目标
二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。
- 例如字母 A 位于坐标 (0,0)，字母 B 位于坐标 (0,1)，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。
给你一个待输入字符串 word，请你计算并返回在仅使用两根手指的情况下，键入该字符串需要的最小移动总距离。
坐标 (x1,y1) 和 (x2,y2) 之间的 距离 是 |x1 - x2| + |y1 - y2|。
注意，两根手指的起始位置是零代价的，不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。
示例 1：
输入：word = "CAKE"
输出：3
解释：
使用两根手指输入 "CAKE" 的最佳方案之一是：
手指 1 在字母 'C' 上 -> 移动距离 = 0
手指 1 在字母 'A' 上 -> 移动距离 = 从字母 'C' 到字母 'A' 的距离 = 2
手指 2 在字母 'K' 上 -> 移动距离 = 0
手指 2 在字母 'E' 上 -> 移动距离 = 从字母 'K' 到字母 'E' 的距离 = 1
总距离 = 3示例 2：
输入：word = "HAPPY"
输出：6
解释：
使用两根手指输入 "HAPPY" 的最佳方案之一是：
手指 1 在字母 'H' 上 -> 移动距离 = 0
手指 1 在字母 'A' 上 -> 移动距离 = 从字母 'H' 到字母 'A' 的距离 = 2
手指 2 在字母 'P' 上 -> 移动距离 = 0
手指 2 在字母 'P' 上 -> 移动距离 = 从字母 'P' 到字母 'P' 的距离 = 0
手指 1 在字母 'Y' 上 -> 移动距离 = 从字母 'A' 到字母 'Y' 的距离 = 4
总距离 = 6说明：
- 2 <= word.length <= 300
- 每个 word[i] 都是一个大写英文字母。
提示：
- dp[i][j][k]: smallest movements when you have one finger on i-th char and the other one on j-th char already having written k first characters from word.
思路
使用两个手指录入 word 字符串，求移动距离的最小值。坐标 (x1, y1) 和 (x2, y2) 之间的 距离 是 |x1 - x2| + |y1 - y2|。字母的坐标见第一张图，起始位置的代价是 0。
定义 dp[i][c] 表示已录入 word[0 ~ i] 且另一个手指在字母 c 的最小移动距离。
假设当前字母编号 cur = word[i] - 'A', 前一个位置的字母编号 prev = word[i - 1] - 'A'，有 dp[i][c] = Math.min(dp[i - 1][c] + dis[prev][cur], dp[i - 1][cur] + dis[prev][c])。
已录入 word[0 ~ i] 两个手指的所在的字母一个是 cur，一个是 c，可以从两个状态转移过来：
- 一手指在字母 c 不动，一根手指从 prev 移动到 cur
- 一手指在字母 cur 不动，一根手指从 prev 移动到 c
代码
/**
* @date 2026-04-13 10:24
*/
public class MinimumDistance1320 {
public int minimumDistance(String word) {
int n = word.length();
int[][] dp = new int[n][26];
for (int i = 1; i < n; i++) {
int prev = word.charAt(i - 1) - 'A';
int cur = word.charAt(i) - 'A';
for (int c = 0; c < 26; c++) {
dp[i][c] = Math.min(dp[i - 1][c] + dis[prev][cur], dp[i - 1][cur] + dis[prev][c]);
}
}
int res = Integer.MAX_VALUE;
for (int d : dp[n - 1]) {
res = Math.min(res, d);
}
return res;
}
}
性能
