题目大意：
二指输入的的最小距离
二指输入法定制键盘在 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]都是一个大写英文字母。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1320
解题思路分析：
本题是 LEETCODE 1165. Single-Row Keyboard 解题思路分析 的升级版，1165这道题的键盘只有一行，同时只有一只手敲键盘，相对比较简单。
而本题一道动态规划DP的题目，当leetcode的题刷到一定数量后，你会发现大部分DP题目的难度是相对较小的，无论是Hard级别还是其他难度，解题套路都是大同小异，无非分情况递归而已。例如本题，两个手打字，每次打印一个字母时，使用左右哪只手取决于哪种选择会导致全局最优，当前情况下，使用左手的代价为，左手目前所在位置移动到当前字母的距离加上打印剩下所有字母的最优代价，同理使用右手的代价为，右手目前所在位置移动到当前字母的距离加上打印剩下所有字母的最优代价。使用左手和右手的最优代价是其中代价较小的一方，求剩下的所有字母的最优代价交给子问题去解决，子问题的逻辑与当前逻辑完全相同。子问题的终止条件为打印完所有字母。
递归时，我们定义一个递归函数help，参数为当前要打印字母所在单词中的index，以及左手的位置和右手的位置。初始时，左手与右手位置设置在一个任意位置，表示可以不花费代价自由移动。单词index为0。递归函数中，对于任意一层递归，使用左手的代价为，左手位置到当前字母间的距离disLeftHand，此时左手位置变为当前字母所在位置，右手位置不变，将此状态交给子问题去求解打印index+1位字母时的最优解，因此，左手打印当前字母的代价为：
costLeftHand = disLeftHand + help(index+1, 当前字母位置，右手原先位置)
同理，使用右手的话，打印代价为：
costRightHand = disRightHand + help(index+1,左手原先位置，当前字母位置)
对于当前两种选择（使用左手或是右手），最优解应该是：
min = min(costLeftHand， costRightHand);
以上即是本题的基本思路。另外对于求两个字母间距离的方法也不难，题目中给出的键盘为一行6个字母，我们使用0-25代表字母A-Z，那么对于任意两个字母的行间差为：
abs(字母1 / 6 - 字母2 / 6)
列间差为：
abs(字母1 % 6 - 字母2 % 6)
举个例子，比如H和U之间的距离，H用7表示，U用20表示，行间差为abs(7/6-20/6)=2。列间差为abs(7%6-20%6)=1。因此，H到U的距离为2+1=3。
实现代码：
Integer[][][] memo; // 记忆数组
public int minimumDistance(String word) {
// 初始化记忆数组
memo=new Integer[word.length()][27][27];
// 递归求解
return help(word,0,26,26);
}
// word为题目给出的单词
// index为当前要打印的字母在word中的下标
// left为左手所在键盘位置
// right为右手所在键盘位置
int help(String word, int index, int left, int right){
// 如果index等于字符串长度，说明所有字母已经打完，返回0
if(index==word.length()) return 0;
// 如果记忆数组中存在当前解，直接返回
if(memo[index][right][left]!=null) return memo[index][right][left];
// 当前字母
int currentChar = word.charAt(index)-'A';
// 移动左手的代价
int leftCost=0;
// 当前左手在26时，代表在键盘外可随意移动，代价为0
// 当左手在键盘内
if(left!=26){
// 左手与当前字母的列差
int diffX = Math.abs(left%6-currentChar%6);
// 左手与当前字母的行差
int diffY = Math.abs(left/6-currentChar/6);
// 移动左手的代价
leftCost=diffX+diffY;
}
// 同理移动右手的代价
int rightCost=0;
if(right!=26){
int diffX = Math.abs(right%6-currentChar%6);
int diffY = Math.abs(right/6-currentChar/6);
rightCost=diffX+diffY;
}
// 当前位置移动左手加上打印剩下字母的代价，与当前位置移动右手加上打印剩下字母的代价中
// 代价较小的一方为当前最优解
int res = Math.min(leftCost+help(word,index+1,currentChar,right),
rightCost+help(word,index+1,left,currentChar));
// 将当前最优解保存至记忆数组
memo[index][right][left]=res;
return res;
}本题解法执行时间为为14ms。
Runtime: 14 ms, faster than 81.60% of Java online submissions for Minimum Distance to Type a Word Using Two Fingers.
Memory Usage: 37.7 MB, less than 100.00% of Java online submissions for Minimum Distance to Type a Word Using Two Fingers.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1320-minimum-distance-to-type-a-word-using-two-fingers-解题思路分析/