C++刷LeetCode（1320. 二指输入的的最小距离）【动态规划】

糖逗

题目描述：

1. 
   
2. 二指输入法定制键盘在 XY 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处，例如字母 A 位于坐标 (0,0)，字母 B 位于坐标 (0,1)，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。
   
3. 
   
4. 给你一个待输入字符串 word，请你计算并返回在仅使用两根手指的情况下，键入该字符串需要的最小移动总距离。坐标 (x1,y1) 和 (x2,y2) 之间的距离是 |x1 - x2| + |y1 - y2|。 
   
5. 
   
6. 注意，两根手指的起始位置是零代价的，不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。
   
7. 
   
8.  
   
9. 
   
10. 示例 1：
    
11. 
    
12. 输入：word = "CAKE"
    
13. 输出：3
    
14. 解释：
    
15. 使用两根手指输入 "CAKE" 的最佳方案之一是：
    
16. 手指 1 在字母 'C' 上 -> 移动距离 = 0
    
17. 手指 1 在字母 'A' 上 -> 移动距离 = 从字母 'C' 到字母 'A' 的距离 = 2
    
18. 手指 2 在字母 'K' 上 -> 移动距离 = 0
    
19. 手指 2 在字母 'E' 上 -> 移动距离 = 从字母 'K' 到字母 'E' 的距离  = 1
    
20. 总距离 = 3
    
21. 示例 2：
    
22. 
    
23. 输入：word = "HAPPY"
    
24. 输出：6
    
25. 解释：
    
26. 使用两根手指输入 "HAPPY" 的最佳方案之一是：
    
27. 手指 1 在字母 'H' 上 -> 移动距离 = 0
    
28. 手指 1 在字母 'A' 上 -> 移动距离 = 从字母 'H' 到字母 'A' 的距离 = 2
    
29. 手指 2 在字母 'P' 上 -> 移动距离 = 0
    
30. 手指 2 在字母 'P' 上 -> 移动距离 = 从字母 'P' 到字母 'P' 的距离 = 0
    
31. 手指 1 在字母 'Y' 上 -> 移动距离 = 从字母 'A' 到字母 'Y' 的距离 = 4
    
32. 总距离 = 6
    
33. 示例 3：
    
34. 
    
35. 输入：word = "NEW"
    
36. 输出：3
    
37. 示例 4：
    
38. 
    
39. 输入：word = "YEAR"
    
40. 输出：7
    
41.  
    
42. 
    
43. 提示：
    
44. 
    
45. 2 <= word.length <= 300
    
46. 每个 word[i]&#160;都是一个大写英文字母。
    
47. 
    
48. 来源：力扣（LeetCode）
    
49. 链接：https://leetcode-cn.com/problems/minimum-distance-to-type-a-word-using-two-fingers
    
50. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int distance(int i, int j){
   
4.         int col1 = i / 6, row1 = i % 6;
   
5.         int col2 = j / 6, row2 = j % 6;
   
6.         return abs(col1 - col2) + abs(row1 - row2);
   
7.     }
   
8.     int minimumDistance(string word) {
   
9.         int len = word.size();
   
10.         vector<vector<vector<int> > >dp(len, vector<vector<int> >(27, vector<int>(27, INT_MAX)));
    
11.         dp[0][word[0]-'A'+1][0] = 0;//输入第一个字符给左手指
    
12.         int res = INT_MAX;
    
13.         for(int i = 1; i < len; i++){
    
14.             int curr = word[i] - 'A' + 1;
    
15.             for(int left = 1; left <= 26; left++){
    
16.                 for(int right = 0; right <= 26; right++){
    
17.                     if(dp[i-1][left][right] != INT_MAX){
    
18.                         //移动左指
    
19.                         dp[i][curr][right] = min(dp[i][curr][right], dp[i-1][left][right] + distance(left-1, curr-1));
    
20.                         //移动右指
    
21.                         if(right == 0){
    
22.                             dp[i][left][curr] = min(dp[i][left][curr], dp[i-1][left][right]);//第一次输入没有成本
    
23.                         }else if(right > 0){
    
24.                             dp[i][left][curr] = min(dp[i][left][curr], dp[i-1][left][right] + distance(right-1, curr-1));
    
25.                         }
    
26.                     }
    
27.                     if(i == len - 1){
    
28.                         res = min(res, min(dp[i][curr][right], dp[i][left][curr]));
    
29.                     }
    
30.                 }
    
31.             }
    
32.         }
    
33.         return res;
    
34.     }
    
35. };

复制代码

参考链接：https://leetcode-cn.com/problems ... zhu-shi-by-kobe24o/

糖逗