一、Problem

You have a keyboard layout as shown above in the XY plane, where each English uppercase letter is located at some coordinate, for example, the letter A is located at coordinate (0,0), the letter B is located at coordinate (0,1), the letter P is located at coordinate (2,3) and the letter Z is located at coordinate (4,1).

Given the string word, return the minimum total distance to type such string using only two fingers. The distance between coordinates (x1,y1) and (x2,y2) is |x1 - x2| + |y1 - y2|.

Note that the initial positions of your two fingers are considered free so don’t count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.

Input: word = "CAKE"
Output: 3
Explanation: 
Using two fingers, one optimal way to type "CAKE" is: 
Finger 1 on letter 'C' -> cost = 0 
Finger 1 on letter 'A' -> cost = Distance from letter 'C' to letter 'A' = 2 
Finger 2 on letter 'K' -> cost = 0 
Finger 2 on letter 'E' -> cost = Distance from letter 'K' to letter 'E' = 1 
Total distance = 3

Constraints:

2 <= word.length <= 300
Each word[i] is an English uppercase letter.

二、Solution

方法一：dp

• 定义状态：
  • $f[i][j][k]$ 表示按下第 $i$ 个字符时，左指尖在位置 $j$，右指尖在位置 $k$ 时的最小移动代价
• 思考初始化：
  • $f[1...n][0...26][0...26] = INF$
• 思考状态转移方程：
  • 如果 $f[i-1][j][k] != INF$：
    • $f[i][p][k] = min(f[i][p][k] ，f[i-1][j][k] + dist(j, p))$，$f[i-1][j][k] + dist(j, p)$ 表示左指尖上一次的位置在 $j$ 处，为了按下第 $i$ 个字符，左指尖从 $j$ 处移动到 $p$ 处需要的代价
    • $f[i][j][p] = min(f[i][j][p] ，f[i-1][j][k] + dist(k, p))$，$f[i-1][j][k] + dist(j, p)$ 表示右指尖上一次的位置在 $k$ 处，为了按下第 $i$ 个字符，右指尖从 $j$ 处移动到 $p$ 处需要的代价
• 思考输出：$min(f[n][0...26][0...26])$ 表示按下第 n 个字符时，左右手的位置是不确定的，所以需要枚举所有情况。

注：$j、k$ 分别是左右指尖上一次所在的位置；因为表格中的字符都是连续的，所以可直接用 26 个字母的编号 v ∈ [0, 25] 来代替网格的坐标运算，在计算坐标时可以用 v/6、v%6 的方式获取点的坐标 x、y

class Solution {int dist(int a, int b) {int x1 = a / 6, y1 = a % 6;int x2 = b / 6, y2 = b % 6;return Math.abs(x1-x2) + Math.abs(y1-y2);}public int minimumDistance(String word) {char[] cs = word.toCharArray();int n = cs.length, INF = 0x3f3f3f3f, f[][][] = new int[n+1][26][26];	//利用字符编号代替坐标点for (int i = 1; i <= n; i++)for (int j = 0; j < 26; j++) {Arrays.fill(f[i][j], INF);}for (int i = 1; i <= n; i++) for (int j = 0; j < 26; j++) for (int k = 0; k < 26; k++) {int p = cs[i-1] - 'A';if (f[i-1][j][k] != INF) {f[i][p][k] = Math.min(f[i][p][k], f[i-1][j][k] + dist(j, p));	//移动左指f[i][j][p] = Math.min(f[i][j][p], f[i-1][j][k] + dist(k, p));	//移动右指}}int min = INF;for (int j = 0; j < 26; j++) for (int k = 0; k < 26; k++) if (f[n][j][k] < min) {min = f[n][j][k];}return min;}
}

复杂度分析

• 时间复杂度：$O(26^2 × n)$，
• 空间复杂度：$O(26^2 × n)$，

---

方法二：空间压缩

按下第 $i$ 个字符的状态只和按下第 $i-1$ 个字符的状态有关，所以可利用滚动思想，将 dp 数组的第一维从 n 压缩成 2

...代办

复杂度分析

• 时间复杂度：$O(n)$，
• 空间复杂度：$O(26^2)$，