T1320.二指输入的的最小距离

dp, https://leetcode.cn/problems/minimum-distance-to-type-a-word-using-two-fingers/

二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。

例如字母 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

提示：

2 <= word.length <= 300
每个 word[i] 都是一个大写英文字母。

状态定义

我们定义 $d p [k] [i] [j]$ 为：

$k$ ：当前已经输入到了 word 的第 $k$ 个字符（从 0 开始）。
$i$ ：第一根手指当前所在的字母下标（0-25 代表 A-Z，26 代表尚未放在键盘上）。
$j$ ：第二根手指当前所在的字母下标（0-25 代表 A-Z，26 代表尚未放在键盘上）。

$d p [k] [i] [j]$ 的值表示完成上述状态所需的最小移动总距离。

转移逻辑

假设我们已经输入了前 $k$ 个字符，现在要输入第 $k + 1$ 个字符（即 word[k]）：

移动第一根手指：从位置 $i$ 移动到 word[k]，第二根手指留在 $j$ 不动。
- 新状态： $d p [k + 1] [w o r d [k]] [j]$
- 代价： $d p [k] [i] [j] + dist (i, w o r d [k])$
移动第二根手指：从位置 $j$ 移动到 word[k]，第一根手指留在 $i$ 不动。
- 新状态： $d p [k + 1] [i] [w o r d [k]]$
- 代价： $d p [k] [i] [j] + dist (j, w o r d [k])$
注意：根据规则，如果手指从初始状态（26）开始移动，代价为 0。
Python 代码实现
为了节省空间，我们注意到 $d p [k + 1]$ 只依赖于 $d p [k]$ ，所以可以用滚动数组的思想，只保留当前状态的二维矩阵。

python

class Solution:
    def minimumDistance(self, word: str) -> int:
        n = len(word)
        
        # 计算曼哈顿距离的辅助函数
        def get_dist(p1, p2):
            if p1 == 26 or p2 == 26: # 26 代表手指还没放在键盘上，代价为 0
                return 0
            r1, c1 = divmod(p1, 6)
            r2, c2 = divmod(p2, 6)
            return abs(r1 - r2) + abs(c1 - c2)

        # 单词转为数字 0-25
        chars = [ord(c) - ord('A') for c in word]
        
        # 初始化 DP 表，dp[i][j] 表示一根手指在 i，另一根在 j 的最小代价
        # 初始时，两根手指都在 26 位置，距离为 0
        dp = {(26, 26): 0}

        for char_idx in chars:
            new_dp = {}
            for (f1, f2), dist in dp.items():
                # 选择 1: 移动第一根手指到 char_idx
                d1 = dist + get_dist(f1, char_idx)
                if (char_idx, f2) not in new_dp or d1 < new_dp[(char_idx, f2)]:
                    new_dp[(char_idx, f2)] = d1
                
                # 选择 2: 移动第二根手指到 char_idx
                d2 = dist + get_dist(f2, char_idx)
                if (f1, char_idx) not in new_dp or d2 < new_dp[(f1, char_idx)]:
                    new_dp[(f1, char_idx)] = d2
            dp = new_dp

        return min(dp.values())

为什么这种定义更容易理解？

具象化：它完整记录了两个“实体”（手指）的位置。你可以想象两个点在棋盘上跳动。
无跳跃逻辑：每一步迭代都对应输入 word 的一个字符，逻辑链条非常完整：
- word[0] 敲完了，手指在哪里？
- word[1] 敲完了，手指在哪里？
- ...以此类推。
自然处理起始代价：通过引入第 27 个位置（索引 26），把“手指还没放上去”这个特殊情况变成了普通的坐标计算，不需要在循环里写复杂的 if-else 判断。

复杂度分析

时间复杂度： $O (N \times Σ^{2})$ ，其中 $N$ 是单词长度， $Σ$ 是字母表大小（26）。虽然理论上是 $26 \times 26$ ，但实际上在每一层 $k$ ，其中一根手指必然在 word[k-1] 上，所以有效的状态数其实只有 $O (26)$ 个。
空间复杂度： $O (Σ^{2})$ 。使用字典或二维数组存储当前状态。即使不优化掉 $k$ 维度，空间复杂度 $300 \times 27 \times 27$ 也在可接受范围内。

这是一个典型的动态规划（DP）问题。

核心思路：

状态定义：当我们键入字符串 word 的第 $i$ 个字符时，其中一根手指必然位于 word[i]。因此，我们只需要记录另一根手指的位置即可。定义 dp[j] 为：键入当前字符后，另一根手指位于字母 $j$ 时的最小移动距离。其中 $j$ 的取值范围是 $0 - 25$ （代表 A-Z），额外增加一个状态（例如 $26$ ）表示这根手指尚未放置在键盘上（起始距离为 0）。
状态转移：假设当前键入到了 word[i-1]，现在要键入 word[i]。设 prev = word[i-1]，curr = word[i]。在处理 curr 之前，我们的状态是 dp[other]，表示一根手指在 prev，另一根在 other。键入 curr 有两种选择：
- 移动已经在 prev 的手指：从 prev 移动到 curr。另一根手指位置不变。新距离 = dp[other] + distance(prev, curr)
- 移动在 other 的手指：从 other 移动到 curr。原本在 prev 的手指现在变成了“另一根手指”。新距离 = dp[other] + distance(other, curr)
坐标映射：字母对应的数字为 n = ord(char) - ord('A')。行坐标：r = n // 6，列坐标：c = n % 6。
Python 代码实现：

python

class Solution:
    def minimumDistance(self, word: str) -> int:
        # 计算两个字母下标之间的曼哈顿距离
        def get_dist(idx1, idx2):
            if idx1 == 26 or idx2 == 26:
                return 0
            r1, c1 = divmod(idx1, 6)
            r2, c2 = divmod(idx2, 6)
            return abs(r1 - r2) + abs(c1 - c2)

        # 将单词转换为 0-25 的数字序列
        nums = [ord(c) - ord('A') for c in word]
        
        # dp[j] 表示当一根手指在当前字符上时，另一根手指在字母 j 上的最小距离
        # 初始状态：第一根手指在 nums[0]，第二根手指还没放（用 26 表示）
        # 此时总距离为 0
        dp = {26: 0}
        
        for i in range(len(nums) - 1):
            curr_pos = nums[i]
            next_pos = nums[i+1]
            new_dp = {}
            
            for other_pos, total_dist in dp.items():
                # 情况 1：移动原本在 curr_pos 的手指去 next_pos
                # 另一根手指位置不变，仍为 other_pos
                d1 = total_dist + get_dist(curr_pos, next_pos)
                if d1 < new_dp.get(other_pos, float('inf')):
                    new_dp[other_pos] = d1
                
                # 情况 2：移动原本在 other_pos 的手指去 next_pos
                # 另一根手指位置变为 curr_pos
                d2 = total_dist + get_dist(other_pos, next_pos)
                if d2 < new_dp.get(curr_pos, float('inf')):
                    new_dp[curr_pos] = d2
            
            dp = new_dp
            
        return min(dp.values())

复杂度分析：

时间复杂度： $O (N \times Σ)$ ，其中 $N$ 是字符串的长度， $Σ$ 是字母表的大小（26）。在每一步中，我们最多遍历 26 个状态。 $300 \times 26 = 7800$ ，效率非常高。
空间复杂度： $O (Σ)$ 。我们只维护了当前步和上一步的状态，空间占用极小。

关键点解释：

初始零代价：代码中通过 if idx1 == 26 or idx2 == 26: return 0 完美处理了“手指起始位置零代价”的规则。当第二根手指从未被使用时，它从位置 26 移动到任何地方的距离都是 0。
状态压缩：由于每一位字符都必须被按下，所以一根手指的位置是确定的（就是当前的 word[i]），这使得我们可以把二维 DP 降阶为一维。

T1320.二指输入的的最小距离 ​

T1320.二指输入的的最小距离