二指输入的的最小距离

题目链接：二指输入的的最小距离

经过几天的冥思苦想，终于想明白了！记录一下代码：

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]）
         * 3、字符只能按顺序输入
         */
        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);
    }
}

结合了这个题解：宝宝也能看懂的 leetcode 题解 - 一维DP数组