题目

二指输入法定制键盘在 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数组

解法

class Solution {
    public int minimumDistance(String word) {
        int n = word.length();
        /*
         * dp数组的三个维度分别表示：[当前输入到第几个字符][左手在第几个字符i][右手在第几个字符j]
         * 可以得到下面两个信息：
         * 1、两个手不可能同时放在最后输入的字符上（也就是不可能出现dp[3][3][3]这种情况）
         * 2、左右手的顺序可以互换（也就是dp[3][0][3]==dp[3][3][0]）
         */
        int[][][] dp = new int[n + 1][n + 1][n + 1];

        // 初始化第一个字符，左手不动，右手放在第一个字符上
        dp[1][0][1] = 0;
        for (int i = 2; i <= n; i++) {
            /*
             * 假设输入到第5个字符，可能的状态有：
             * 1、dp[5][0][5]：左手没用过，右手停在第5个字符，这种情况只能来自dp[4][0][4];
             * 2、dp[5][1][5]：左手停在第1个字符，右手停在第5个字符，这种情况只能来自dp[4][1][4]；
             * 3、dp[5][2][5] <-- dp[4][2][4]
             * 4、dp[5][3][5] <-- dp[4][3][4]
             * 5、dp[5][4][5]：这种情况就比较复杂了，首先不能来自dp[4][4][4]，因为左右手不可能都停在第4个字符，所以它可能来自下面几种情况，取最小值。
             *      1）dp[4][4][0]：前4个都用的左手，到第5个直接用右手。dp[5][5][4]=dp[4][4][0]+0;
             *      2）dp[4][4][1]：之前左手在第4个字符，右手在第1个字符。dp[5][5][4]=dp[4][4][1]+dis(word[1],word[5])，右手从第1个字符到第5个字符
             *      3）dp[4][4][2]：dp[5][5][4]=dp[4][2][4]+dis(word[2],word[5]);
             *      4）dp[4][4][3]：dp[5][5][4]=dp[4][4][3]+dis(word[3],word[5]);
             *      因为左右手可以替换，dp[5][5][4]=dp[5][4][5]，dp[4][4][0]=dp[4][0][4];
             *
             */
            // 求dp[i][0][i]到dp[i][i-2][i];
            for (int j = 0; j < i - 1; j++) {
                dp[i][j][i] = dp[i - 1][j][i - 1] + dis(word.charAt(i - 2), word.charAt(i - 1));
            }
            // 求dp[i][i-1][i]
            dp[i][i - 1][i] = dp[i - 1][0][i - 1];
            for (int j = 1; j < i - 1; j++) {
                dp[i][i - 1][i] = Math.min(dp[i][i - 1][i], dp[i - 1][j][i - 1] + dis(word.charAt(j - 1), word.charAt(i - 1)));
            }
        }

        // 求dp[n][0][n]到dp[n][n-1][n]的最小值
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, dp[n][i][n]);
        }
        return ans;
    }

    int dis(char c1, char c2) {
        int a = c1 - 'A';
        int b = c2 - 'A';
        return Math.abs(a / 6 - b / 6) + Math.abs(a % 6 - b % 6);
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现