LeetCode 1320. 二指輸入的的最小距離（動態規劃）

1. 題目

二指輸入法客製化鍵盤在 XY 平面上的佈局如上圖所示，其中每個大寫英文字母都位於某個座標處，
例如字母 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

範例 3：
輸入：word = "NEW"
輸出：3

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

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/minimum-distance-to-type-a-word-using-two-fingers
著作權歸領釦網路所有。商業轉載請聯絡官方授權，非商業轉載請註明出處。

2. 解題

• dp[i][c1][c2] 表示輸入完 i 字元后，手指1在 c1 字元，手指2在 c2 字元（0表示還沒有輸入字元，1-26表示A-Z）時的最小移動距離

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;
    }
};

32 ms 7.5 MB

---

我的CSDN部落格地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！