LeetCode 1320. 二指输入的的最小距离（动态规划）

示例 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

示例 3：
输入：word = "NEW"
输出：3

示例 4：
输入：word = "YEAR"
输出：7
 
提示：
2 <= word.length <= 300
每个 word[i] 都是一个大写英文字母。

class Solution {
public:
    int minimumDistance(string s) {
        vector<vector<int>> pos(27, vector<int>(2));
        int count = 1;
        for(int i = 0; i < 5 && count < 27; ++i)
            for(int j = 0; j < 6 && count < 27; ++j)
            {
                pos[count++] = {i, j};//字符的坐标
            }
        int n = s.size(), mindis = INT_MAX;
        int dp[301][27][27];
        memset(dp, 0x7f, sizeof(dp));
        dp[0][s[0]-'A'+1][0] = 0;//输入第一个字符给手指1
        for(int i = 1; i < n; ++i)
        {	//剩余字符
            int c = s[i]-'A'+1;//当前字符序号 1-26
            for(int c1 = 1; c1 <= 26; ++c1)
            {
                for(int c2 = 0; c2 <= 26; ++c2)
                {
                    if(dp[i-1][c1][c2] == 0x7f7f7f7f)
                        continue;//状态不存在
                    // 当前字母c由第1个手指输入
                    dp[i][c][c2] = min(dp[i][c][c2], dp[i-1][c1][c2]+abs(pos[c][0]-pos[c1][0])+abs(pos[c][1]-pos[c1][1]));
                    // 当前字母c由第2个手指输入
                    if(c2 == 0)//第二个手指还没输入
                        dp[i][c1][c] = min(dp[i][c1][c], dp[i-1][c1][c2]);//第一次输入没有成本
                    else
                        dp[i][c1][c] = min(dp[i][c1][c], dp[i-1][c1][c2]+abs(pos[c][0]-pos[c2][0])+abs(pos[c][1]-pos[c2][1]));
                }
            }
        }
        for(int c1 = 1; c1 <= 26; ++c1)
            for(int c2 = 0; c2 <= 26; ++c2)
                mindis = min(mindis, dp[n-1][c1][c2]);
        return mindis;
    }
};