Leetcode每日一题 —— 1320. 二指输入的的最小距离

问题描述：

力扣 LeetCode

1320. 二指输入的的最小距离 - 力扣（LeetCode）

1320. 二指输入的的最小距离 - [https://assets.leetcode.cn/aliyun-lc-upload/uploads/2020/01/11/leetcode_keyboard.png] 二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。 * 例如字母A位于坐标(0,0)，字母B位于坐标(0,1)，字母P位于坐标(2,3)且字母...

思路

看上去是困难题，但是先别慌，输入规模不算很大，可以先试试 DFS 和记忆化。

首先要搞清楚我们要维护某一时刻的哪些状态：

1. 手指 1 落在的字符
2. 手指 2 落在的字符
3. 已经输入到了 word 中的哪个字符

可以看到我们可以顺着“输入 word 中的字符”这条路来拆分子问题来递归求解：每要输入一个字符时，要不用第一根手指，要不用第二根手指。

值得注意的一点是，为了让初始代价最小，手指输入的第一个字符的代价可以忽略掉（假设这根手指最开始就在这个字符上）。

怎么判断手指是不是第一次输入呢？咱的想法是在 0-25 之外再加个状态值 26，用 26 表示手指还没输入过一个字符。

直接用 DFS 很容易超时，幸运的是上面我们把状态找出来后，做记忆化就很容易了，开个 memo[n][27][27] 数组即可。