1320. 二指输入的的最小距离

二指输入法定制键盘在 XY 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处，例如字母 A 位于坐标 (0,0)，字母 B 位于坐标 (0,1)，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。

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

注意，两根手指的起始位置是零代价的，不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。

示例 1：

1
2
输入：word = "CAKE"
输出：3

解释：
使用两根手指输入 “CAKE” 的最佳方案之一是：
手指 1 在字母 ‘C’ 上 -> 移动距离 = 0
手指 1 在字母 ‘A’ 上 -> 移动距离 = 从字母 ‘C’ 到字母 ‘A’ 的距离 = 2
手指 2 在字母 ‘K’ 上 -> 移动距离 = 0
手指 2 在字母 ‘E’ 上 -> 移动距离 = 从字母 ‘K’ 到字母 ‘E’ 的距离 = 1
总距离 = 3

示例 2：

1
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

示例 3：

1
2
输入：word = "NEW"
输出：3

示例 4：

1
2
输入：word = "YEAR"
输出：7

提示：
2 <= word.length <= 300
每个 word[i]。都是一个大写英文字母。

Solution1（记忆化）：

我们首先要定义一个递归方程，思考后发现有两类主要元素：第一类是要记录到哪个字符，第二类是两个手指当前的位置。

然后发现“记录到哪个字符”这个状态不太好与两个手指进行关联（只能和一个手指进行绑定），所以我们转化一下思路，将记录到哪个字符转变为从第i个字符起，到字符串的末尾这整个区间，然后记录两个手指的状态。这样就得到了如下的递归函数参数：

1
2
3
4
// i: [i:w.size()]区间内花费的最小距离，
// l: 上一个第一个手指的位置。
// r: 上一个第二个手指的位置
dfs(int i, int l, int r)

转移方程为：

1
dfs(i,l,c) = min(dfs(i+1,l,c)+cost(r,c),dfs(i+1,c,r)+cost(l,c));

然后添加记忆化数组，整理就得到了下面的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:

    int mem[310][27][27];
    int cost(int i, int j){
        if(i == 26 || j == 26) return 0;
        return abs(i/6-j/6)+abs(i%6-j%6);
    }
    string w;
    // i: [i:w.size()]区间内花费的最小距离，
    // l: 上一个第一个手指的位置。
    // r: 上一个第二个手指的位置。
    int dfs(int i, int l, int r){
        if(i == w.size()) return 0;
        if(mem[i][l][r]) return mem[i][l][r];
        int c = w[i]-'A';
        return mem[i][l][r] = min(dfs(i+1,l,c)+cost(r,c),dfs(i+1,c,r)+cost(l,c));
    }
    int minimumDistance(string word) {
        w = word;
        //计算整个字符串的区间，初始两指从悬空状态开始。
        return dfs(0,26,26);
    }
};

Solution2（DP）：

我们可以试着将记忆化搜索转化为dp求解，很明显，状态表示和递归函数的状态是一致的，都是三维表示。

1
int dp[i][j][k]; //第一个手指一动到i，第二个手指移动到j，已经移动了k个字符的最小代价。

这里与记忆化搜索定义的字符区间范围正好相反，递归中用的是从i到n的区间，而这里由于天然的记忆化过程，可以直接表示从0到k。

接着写状态转移方程：

1
2
3
4
//从上一个字符移动到当前字符使用第一个手指，计算的最小价值。
dp[c][j][k] = min(dp[c][j][k],dp[i][j][k-1] + cost);
//从上一个字符移动到当前字符使用第二个手指，计算的最小价值。
dp[i][c][k] = min(dp[i][c][k],dp[i][j][k-1] + cost);

最后我们查看手指停在任何字符上的代价取最小即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int Cost(int i, int j){
        //悬空状态，代价为0
        if(i == 26 || j == 26) return 0;
        return abs(i/6-j/6)+abs(i%6-j%6);
    }
    int dp[27][27][301]; //第一个手指一动到i，第二个手指移动到j，已经移动了k个字符的最小代价。
    int minimumDistance(string word) {
        memset(dp,0x3f3f3f3f,sizeof(dp));
        // 初始化悬空状态
        dp[26][26][0] = 0;
        int n = word.size();
        for(int k = 1; k <= n; k++){
            int c = word[k-1]-'A';
            //a
            int cost = 0;
            for(int i = 0; i <= 26; i++){
                for(int j = 0; j <= 26; j++){
                    cost = Cost(i,c);
                    //从上一个字符移动到当前字符使用第一个手指，计算的最小价值。
                    dp[c][j][k] = min(dp[c][j][k],dp[i][j][k-1] + cost);
                    cost = Cost(j,c);
                    //从上一个字符移动到当前字符使用第二个手指，计算的最小价值。
                    dp[i][c][k] = min(dp[i][c][k],dp[i][j][k-1] + cost);
                }
            }
        }
        int ans = 0x3f3f3f3f;
        for(int i = 0; i <= 26; i++){
            for(int j = 0; j <= 26; j++){
                ans = min(ans,dp[i][j][n]);
            }
        }
        return ans;
    }
};