AI 的时代焦虑，终于以一种极端的方式落到了现实。
凌晨 3 点 45 分，美国旧金山北滩社区。一枚燃烧瓶砸向大门，火苗蹿起，随即熄灭。住在里面的，是全球最具争议的科技公司掌舵人：OpenAI CEO Sam Altman（山姆·奥特曼）。
幸运的是，燃烧瓶弹开了。没有人受伤。一个多小时后，同一名嫌疑人出现在 OpenAI 旧金山总部门口，扬言要烧掉这栋楼。警方随即将其拘押，一名 20 岁的男性。
这条新闻本来可以就这样结束：「AI 公司高管遭遇袭击，嫌疑人落网，暂无人伤亡。」
但奥特曼没有选择沉默。他于一个小时前发了一篇很长的文章。
「这是我家人的照片。他们是我的一切。」开头就是这句话，配了一张他和伴侣、儿子的合照。他解释为什么要公开这张平时刻意藏起来的照片：「希望能让下一个人在冲我家扔燃烧瓶之前三思，无论他们对我有什么看法。」
然后他说，几天前有一篇「针对我的煽动性文章」，有人提醒过他，那篇文章的发布时机，恰逢公众对 AI 极度焦虑的节点，可能让他陷入更危险的处境。他当时没当回事。
「现在我在深夜辗转难眠，怒火中烧，开始意识到自己低估了文字与叙事的力量。」
这是 AI 时代第一次，一位 CEO 在「有人想烧死我」之后，没有选择报警声明加公关稿的标准流程，而是把这种恐惧、愤怒和反思，原原本本地写出来。
文章分三部分：信念、个人反思、行业思考。
信念部分其实没什么新鲜的。AI 是人类能力的最强扩展工具，必须民主化，权力不能过度集中，社会需要适应机制……这些他说过很多次了。
真正值得停下来读的，是「个人反思」这一段。他说自己「有很多值得骄傲的事，也有不少错误」。
骄傲的是什么？他提到了和马斯克的那场纠纷。
当年马斯克试图对 OpenAI 谋求单方面控制权，奥特曼拒绝了。他说：「我为自己当时守住的那条底线感到自豪，也为我们走出的那条窄路感到自豪，正是那条路让 OpenAI 得以延续。」
不骄傲的是什么？他说自己「回避冲突」，给公司和自己都带来了巨大痛苦。他说在与前任董事会的冲突中「处置失当」，造成了混乱。他说自己是「一个有缺陷的人，身处一个异常复杂的处境」。
对于那些他曾经伤害过的人，他道了歉。
这是这篇文章里最罕见的部分。科技圈的高管道歉，通常要么是 PR 危机后的被迫姿态，要么措辞模糊到没有任何实质性认错。奥特曼这段话说得不算完整，但至少是真实的。
文章最后一部分，他还说他理解过去几年为什么会上演这么多「莎士比亚式戏剧」：「一旦看见 AGI，就再也无法视而不见。它有一种真实的『权力之戒』式动力，会让人做出疯狂之举。」
正如他所理解的那样，成为掌控 AGI 之人这种执念，它能腐蚀任何人。
包括OpenAI 的历史本身就是一部权力争夺的纪录片。马斯克的出走与反目、前董事会的突然解雇风波、微软的深度绑定、Ilya Sutskever 的离开……每一段都牵涉到对「谁掌控 AI 未来」这个问题的不同答案。
奥特曼说，唯一的解法是「把技术向更广泛的人群开放，让任何人都无法独握那枚戒指」。
那名 20 岁的嫌疑人，没有留下任何宣言。
我们不知道他为什么去扔那枚燃烧瓶。是被哪篇文章激怒？是对 AI 夺走工作的恐惧？是某种更私人的偏执？
但这件事本身，代表了一种真实存在的社会情绪。
失业焦虑、技术恐惧、对少数人掌控未来的愤怒，这些情绪在过去两年被 AI 的爆发式发展急剧放大。当 OpenAI 每隔几个月就发布一款能「取代某类工作」的新产品，当 ChatGPT 出现在每个行业的重组报告里，当「你的岗位会被 AI 替代吗」成为刷屏话题，积累下来的东西，总会找到出口。
奥特曼在文章里说，他现在担心的已经不只是「模型对齐」，而是整个社会层面能否及时建立起应对机制。这话听起来像是在为监管松绑找理由，但放在这次事件的语境里，它有另一层意思：
连 AI 公司的 CEO 自己，也开始承认技术的速度已经超出了社会的消化能力。
这不是什么新发现，但由奥特曼在凌晨、在燃烧瓶的余温里说出来，分量就不一样了。过去几年，科技圈惯用的叙事是「我们在解决问题」。监管跟不上？我们自律。就业冲击？我们会创造新岗位。
每一次质疑，都有一套对应的话术。
但燃烧瓶的出现说明，有一部分人的愤怒，已经溢出了「理性讨论」的范围。
暴力当然没有任何正当性。
无论动机如何，向一个熟睡婴儿的家投掷燃烧瓶，都应受到谴责和处罚。虽然警方尚未确认此次袭击是与 AI 反对情绪有关，还是受近期《纽约客》负面报道影响，但这件事本身已折射出 AI 发展带来的社会焦虑正在升温。
那种不安是可以理解的，从没有一项技术像 AI 一样以疯狂的速度改变世界，这种恐惧是真实的。
奥特曼这篇文章，是他少有的一次没有站在「我们在解决问题」的位置上发言。他承认了错误，承认了恐惧，也承认了自己也不完全知道前路在哪里。
人和 AI 应该如何相处，可能是比实现 AGI 更大的难题。
这是我家人的照片。他们是我的一切。
图像有力量，我希望如此。平时我们都很注重隐私，但这次我选择公开这张照片，希望能让下一个人在冲我家扔燃烧瓶之前三思——无论他们对我有什么看法。
第一个人昨晚凌晨 3 点 45 分这么做了。幸好燃烧瓶弹开了，没有人受伤。
文字同样有力量。几天前有一篇针对我的煽动性文章。昨天有人跟我说，他认为这篇文章发布的时机恰逢公众对 AI 极度焦虑之际，可能会让我陷入更危险的处境。我当时没放在心上。
现在我在深夜辗转难眠，怒火中烧，开始意识到自己低估了文字与叙事的力量。趁这个机会，我想说几件事。
一、我的信念
回顾我在 OpenAI 头十年的工作，有很多值得骄傲的事，也有不少错误。
我想起我们即将与埃隆对簿公堂，想起当年我如何坚守底线，拒绝接受他对 OpenAI 谋求的单方面控制权。我为此感到自豪，也为我们当时走出的那条窄路感到自豪——正是那条路让 OpenAI 得以延续，并取得了此后的一切成就。
我并不为自己的回避冲突感到自豪，那给我和 OpenAI 都带来了巨大的痛苦。我也不为自己在与前任董事会的冲突中处置失当、给公司造成混乱感到自豪。OpenAI 走过的历程跌宕起伏，我在其中犯下过许多错误；我是一个有缺陷的人，身处一个异常复杂的处境，每年都在努力变得好一点，始终为这一使命而工作。我们从一开始就清楚 AI 的赌注有多大，也知道善意之人之间的个人分歧会因此被无限放大。但亲历这些激烈的冲突、往往还要在其中充当仲裁者，其代价是沉重的。对于那些我曾经伤害过的人，我深感抱歉，也希望自己能更快从中汲取教训。
我也清醒地意识到，OpenAI 如今已是一个重要的平台，我们需要以更具可预期性的方式运营。过去几年极其紧张、混乱、高压。
但总体而言，我为我们正在兑现使命感到无比自豪——这在当初看来几乎是不可能的。克服重重阻碍，我们摸索出了构建强大 AI 的方法，筹集到了足够的资本来建设交付所需的基础设施，建立起了一家产品公司和商业体系，以大规模提供相当安全、稳健的服务，还有更多。
很多公司都说要改变世界；我们真的做到了。
综观过去几年，我对这个领域为何上演了如此多莎士比亚式戏剧的个人理解是：「一旦看见 AGI，就再也无法视而不见。」 它有一种真实的「权力之戒」式动力，会让人做出疯狂之举。我说的不是 AGI 本身就是那枚戒指，而是「成为掌控 AGI 之人」这种无所不包的执念。
我能想到的唯一解法，是着力于向更广泛的人群开放这项技术，让任何人都无法独握那枚戒指。实现这一目标的两个显而易见的途径，是个体赋权，以及确保民主制度始终掌握主导权。
民主进程的力量必须凌驾于公司之上。法律与规范会不断演变，但我们必须在民主进程的框架内行事，尽管这个过程会混乱、也会比我们期望的更慢。我们希望成为其中的一个声音、一个利益相关方，但不是要独揽一切权力。
业界受到的许多批评，源自人们对这项技术极高风险的真诚忧虑。这种忧虑完全合理，我们欢迎善意的批评与辩论。我理解反技术的情绪，技术的确并非对每个人都始终有益。但从整体来看，我相信技术进步能够让未来变得无与伦比地美好——对你我的家庭都是如此。
在我们进行这场辩论的同时，我们应当共同降低言辞与行动的烈度，让更少的人家——无论是字面意义上还是隐喻意义上——遭遇爆炸。
附上博客地址：
https://blog.samaltman.com/2279512
#欢迎关注爱范儿官方微信公众号：爱范儿（微信号：ifanr），更多精彩内容第一时间为您奉上。
二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。
给你一个待输入字符串 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 <= 300word[i] 都是一个大写英文字母。你有没有这种体验：让 AI 帮你写个页面，它生成的代码颜色全是瞎编的、间距全靠猜、按钮样式跟你们产品完全不搭？
然后你甩给它一份设计规范的 PDF，指望它能“学会”你们的设计体系。
结果呢？AI 看 PDF 基本等于盲人摸象——它看到的是一堆碎片化的文字和完全无法理解的截图。那些精心排版的视觉示例，在 AI 眼里跟噪音差不多。
问题不是 AI 不行，而是我们给 AI 的“学习资料”不对。
传统设计规范长这样：一份精美的 PDF，里面有品牌色卡、组件截图、do/don’t 的对比图、各种排版示例。
这东西给人看，完美。给 AI 看，灾难。
原因很简单：
第一，PDF 是视觉媒介，AI 是文本动物。 PDF 里那些色卡截图，AI 根本“看”不出来里面的色值是什么。它需要的是 #1A73E8 这个字符串，不是一个蓝色方块的图片。
第二，设计规范的“规则”通常是散文式的。 比如“不要在一个页面里放太多主按钮”——这句话人类一看就懂，但 AI 很难把它转化成一个可执行的判断。太多是多少？什么算主按钮？什么算一个页面？
第三，知识是碎片化的。 颜色写在第 3 页，间距写在第 7 页，按钮的规范在第 12 页，而按钮用到的颜色和间距需要 AI 自己去关联。这种跨页面的信息拼装，AI 做起来很吃力。
一句话总结：视觉示例给人看，结构化数据给 AI 读。
具体来说，就是把传统设计规范里的每一个设计决策，都翻译成 AI 能精确解析的格式。
那用什么格式呢？我让 Claude Opus 帮我调研了一下，它推荐的方案是：Markdown + JSON + YAML 的组合。其中：
为什么不统一用一种格式？因为各有所长。JSON 适合定义纯数据（Design Token），YAML 适合描述有层次的组件规范（因为可读性更好），Markdown 适合写需要段落和叙事的内容（设计原则、模式指引）。
传统规范里，设计师说“主色调是品牌蓝”，然后在 PDF 里放一个色块。
AI 友好的方式是把它变成一个 Token：
1 |
{ |
注意这里不只有色值，还有 usage（什么场景用）和 wcag_aa（是否满足无障碍标准）。这些上下文信息对 AI 来说极其重要——它不只要知道“是什么颜色”，还要知道“什么时候用”和“为什么选这个颜色”。
同理，字号、间距、圆角、阴影、动画时长……所有数值类的设计决策，都应该 Token 化。
传统规范里，一个按钮组件的描述可能是一页截图加几段说明文字。
AI 友好的方式是用 YAML 写一个完整的结构化定义：
1 |
component: Button |
这里面有几个关键设计：
用花括号引用 Token，比如 {color.brand.primary}。这样 AI 在生成代码时，会自动去 Token 文件里查对应的值，而不是硬编码一个色值。整个系统是关联的。
明确列出所有状态。人类设计师可能觉得“hover 状态不用说大家都知道”，但 AI 需要你把它列出来。缺什么它就不做什么。
有变体（variants）和尺寸（sizes）的穷举。 AI 最擅长在有限集合里做选择，而不是在模糊描述里做推断。
这是最关键的一步。
传统规范里的“Don’t”通常配一张错误示例截图，AI 完全看不懂。
AI 友好的方式是把它写成带 ID、有严重等级、能机器检查的规则：
1 |
rules: |
这种格式有几个好处：
你的设计规范可能有几十个文件，AI 不知道该先看哪个。你需要一个 README.md 作为入口，就像给 AI 画一张地图：
1 |
## AI 使用指引 |
这个入口文件告诉 AI 三件事：有哪些文件、每个文件是干嘛的、不同任务应该按什么顺序查阅哪些文件。
传统规范里的设计原则通常很抽象：“我们追求简洁”。
AI 友好的方式是让原则可操作——不只说“是什么”，还说“怎么用”和“冲突时怎么办”：
1 |
### 清晰优先于美观 |
特别是要提供一个 原则冲突解决矩阵。比如“清晰”和“包容性”冲突时谁优先？“性能”和“一致性”冲突时呢？人类设计师靠直觉判断，AI 需要明确的规则。
说了这么多，最终的目录结构长这样：
1 |
design-system/ |
每层的分工很清晰：
不要一步到位。 你不需要一次把整个设计规范都改造完。可以先从 Design Token 开始——把颜色和字号从 PDF 里抽出来做成 JSON 文件，这一步投入产出比最高。
保持两个版本同源。 理想情况下，JSON/YAML 是“源文件”，PDF 版本从源文件自动生成。这样改一处，两边都更新。如果做不到自动生成，至少保证人工同步。
给每个决策加上“为什么”。 这是很多人最容易忽略的。AI 在遇到边缘情况时，rationale 字段就是它做判断的依据。没有 rationale，它只会机械执行规则；有了 rationale，它能理解意图，做出更灵活的判断。
把规范放到代码仓库里。 设计规范不应该是一个飞书文档或者 Figma 链接，而是一个 Git 仓库里的文件夹。这样 AI 工具可以直接读取，开发者可以在 CI/CD 里做自动检查，版本变更有迹可循。
实际测试。 改造完之后，拿你的 AI 工具（Claude、Cursor、Copilot 等）实际跑一遍：让它基于你的设计规范生成一个页面，看看它是不是真的引用了 Token、遵守了规则。不好使就迭代。
AI 时代的设计规范，本质上是一个 API——它不再只是给人“阅读”的文档，而是给机器“调用”的接口。
格式变了，但设计的本质没变。你仍然需要好的设计判断来决定什么颜色、什么间距、什么交互模式。只是表达方式要变一变：从“让人看懂”升级为“人机双读”。
如果你的设计师不知道如何输出上面的文件，没关系，把这篇文章发给你的 AI Agent（推荐使用 Claude Opus 4.6），然后说：我需要按照文章中的方案来产生一套面向 AI 的设计规范，你来帮我完成，现在你告诉我需要哪些文件和资料，我来负责提供。
放心，AI 会一步一步带着你完成这份规范。
希望对你有用。
示例 1 的 $\textit{word} = \texttt{CAKE}$，敲完 $\texttt{E}$ 就结束了，所以最后一定有一根手指停在 $\texttt{E}$。
另一根手指呢？最后一定停在 $\texttt{K}$ 吗？不一定，如果第一根手指输入 $\texttt{CA}$，第二根手指输入 $\texttt{KE}$，那么第一根手指最后会停在 $\texttt{A}$，第二根手指最后会停在 $\texttt{E}$。
只要我们能实时跟踪两根手指的位置（在哪个字母），就能暴力搜索所有输入的过程。
根据上面的讨论，定义 $\textit{dfs}(i, \textit{finger}_1, \textit{finger}_2)$ 表示在手指 1 位于字母 $\textit{finger}_1$，手指 2 位于字母 $\textit{finger}_2$ 的情况下，输入 $\textit{word}$ 的前缀 $[0,i]$ 的最小移动总距离。
注：从右往左递归，主要是方便把递归翻译成从左往右的递推。从左往右递归也是可以的。
讨论用哪根手指输入 $\textit{word}[i]$：
这两种情况取最小值，就得到了 $\textit{dfs}(i, \textit{finger}_1, \textit{finger}_2)$，即
$$
\textit{dfs}(i, \textit{finger}_1, \textit{finger}_2) = \min
\begin{cases}
\textit{dfs}(i-1, \textit{word}[i],\textit{finger}_2) + \textit{dis}[\textit{finger}_1][\textit{word}[i]] \
\textit{dfs}(i-1, \textit{finger}_1,\textit{word}[i]) + \textit{dis}[\textit{finger}_2][\textit{word}[i]] \
\end{cases}
$$
其中 $\textit{dis}[x][y]$ 表示从字母 $x$ 到字母 $y$ 的距离。这个二维数组可以在跑 $\textit{dfs}$ 之前预处理出来。
递归边界：$\textit{dfs}(-1, \textit{finger}_1, \textit{finger}_2)=0$。没有字母需要输入，无需移动。
递归入口：$\textit{dfs}(n-2, \textit{word}[n-1], \textit{finger}_2)$。最后一定有一根手指在 $\textit{word}[n-1]$，另一根手指的位置不确定，枚举 $\textit{finger}_2$。
考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：
⚠注意：$\textit{memo}$ 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 $0$，并且要记忆化的 $\textit{dfs}(i, \textit{finger}_1, \textit{finger}_2)$ 也等于 $0$，那就没法判断 $0$ 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 $-1$。
Python 用户可以无视上面这段，直接用
@cache装饰器。
具体请看视频讲解 动态规划入门：从记忆化搜索到递推【基础算法精讲 17】，其中包含把记忆化搜索 1:1 翻译成递推的技巧。
###py
# 预处理两个字母的距离
COLUMN = 6
get_dis = lambda a, b: abs(a // COLUMN - b // COLUMN) + abs(a % COLUMN - b % COLUMN)
dis = [[get_dis(i, j) for j in range(26)] for i in range(26)]
class Solution:
def minimumDistance(self, word: str) -> int:
word = [ord(ch) - ord('A') for ch in word] # 避免在 dfs 中频繁调用 ord
@cache # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
def dfs(i: int, finger1: int, finger2: int) -> int:
if i < 0:
return 0
# 手指 1 移到 word[i]
res1 = dfs(i - 1, word[i], finger2) + dis[finger1][word[i]]
# 手指 2 移到 word[i]
res2 = dfs(i - 1, finger1, word[i]) + dis[finger2][word[i]]
return min(res1, res2)
n = len(word)
# 最后一定有一根手指在 word[-1]，另一根手指的位置不确定，枚举
return min(dfs(n - 2, word[-1], finger2) for finger2 in range(26))
###java
class Solution {
private static final int[][] dis = new int[26][26];
static {
// 预处理两个字母的距离
final int COLUMN = 6;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
dis[i][j] = Math.abs(i / COLUMN - j / COLUMN) + Math.abs(i % COLUMN - j % COLUMN);
}
}
}
public int minimumDistance(String word) {
char[] s = word.toCharArray();
int n = s.length;
int[][][] memo = new int[n][26][26];
for (int[][] mat : memo) {
for (int[] row : mat) {
Arrays.fill(row, -1); // -1 表示没有计算过
}
}
int ans = Integer.MAX_VALUE;
// 最后一定有一根手指在 s[n-1]，另一根手指的位置不确定，枚举
for (int finger2 = 0; finger2 < 26; finger2++) {
ans = Math.min(ans, dfs(n - 2, s[n - 1] - 'A', finger2, s, memo));
}
return ans;
}
private int dfs(int i, int finger1, int finger2, char[] word, int[][][] memo) {
if (i < 0) {
return 0;
}
if (memo[i][finger1][finger2] != -1) { // 之前计算过
return memo[i][finger1][finger2];
}
// 手指 1 移到 word[i]
int w = word[i] - 'A';
int res1 = dfs(i - 1, w, finger2, word, memo) + dis[finger1][w];
// 手指 2 移到 word[i]
int res2 = dfs(i - 1, finger1, w, word, memo) + dis[finger2][w];
int res = Math.min(res1, res2);
memo[i][finger1][finger2] = res; // 记忆化
return res;
}
}
###cpp
int dis[26][26];
auto init = [] {
// 预处理两个字母的距离
constexpr int COLUMN = 6;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
dis[i][j] = abs(i / COLUMN - j / COLUMN) + abs(i % COLUMN - j % COLUMN);
}
}
return 0;
}();
class Solution {
public:
int minimumDistance(string word) {
int n = word.size();
vector memo(n, vector(26, vector<int>(26, -1))); // -1 表示没有计算过
auto dfs = [&](this auto&& dfs, int i, int finger1, int finger2) -> int {
if (i < 0) {
return 0;
}
int& res = memo[i][finger1][finger2]; // 注意这里是引用
if (res != -1) { // 之前计算过
return res;
}
// 手指 1 移到 word[i]
int w = word[i] - 'A';
int res1 = dfs(i - 1, w, finger2) + dis[finger1][w];
// 手指 2 移到 word[i]
int res2 = dfs(i - 1, finger1, w) + dis[finger2][w];
res = min(res1, res2);
return res;
};
int ans = INT_MAX;
// 最后一定有一根手指在 word[n-1]，另一根手指的位置不确定，枚举
for (int finger2 = 0; finger2 < 26; finger2++) {
ans = min(ans, dfs(n - 2, word[n - 1] - 'A', finger2));
}
return ans;
}
};
###go
var dis [26][26]int
func init() {
// 预处理两个字母的距离
const column = 6
for i := range 26 {
for j := range 26 {
dis[i][j] = abs(i/column-j/column) + abs(i%column-j%column)
}
}
}
func minimumDistance(word string) int {
n := len(word)
memo := make([][26][26]int, n)
var dfs func(int, byte, byte) int
dfs = func(i int, finger1, finger2 byte) (res int) {
if i < 0 {
return 0
}
p := &memo[i][finger1][finger2]
if *p != 0 { // 之前计算过
return *p - 1
}
defer func() { *p = res + 1 }() // 记忆化的时候加一，这样就无需初始化 memo 为 -1 了
// 手指 1 移到 word[i]
w := word[i] - 'A'
res1 := dfs(i-1, w, finger2) + dis[finger1][w]
// 手指 2 移到 word[i]
res2 := dfs(i-1, finger1, w) + dis[finger2][w]
return min(res1, res2)
}
ans := math.MaxInt
// 最后一定有一根手指在 word[n-1]，另一根手指的位置不确定，枚举
for finger2 := range byte(26) {
ans = min(ans, dfs(n-2, word[n-1]-'A', finger2))
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
不计入预处理的时间和空间。
回顾上面的代码，在输入 $\textit{word}[i]$ 之前，一定有一根手指在 $\textit{word}[i+1]$。这意味着，知道了 $i$，就知道了其中一根手指的位置。所以 $\textit{finger}_1$ 和 $\textit{finger}_2$ 中的一个是多余的。
定义 $\textit{dfs}(i, \textit{anotherFinger})$ 表示在一根手指位于字母 $\textit{word}[i+1]$，另一根手指位于字母 $\textit{anotherFinger}$ 的情况下，输入 $\textit{word}$ 的前缀 $[0,i]$ 的最小移动总距离。
讨论用哪根手指输入 $\textit{word}[i]$：
这两种情况取最小值，就得到了 $\textit{dfs}(i, \textit{anotherFinger})$，即
$$
\textit{dfs}(i, \textit{anotherFinger}) = \min
\begin{cases}
\textit{dfs}(i-1, \textit{anotherFinger}) + \textit{dis}[\textit{word}[i+1]][\textit{word}[i]] \
\textit{dfs}(i-1, \textit{word}[i+1]) + \textit{dis}[\textit{anotherFinger}][\textit{word}[i]] \
\end{cases}
$$
递归边界：$\textit{dfs}(-1, \textit{anotherFinger})=0$。没有字母需要输入，无需移动。
递归入口：$\textit{dfs}(n-2, \textit{anotherFinger})$。最后一定有一根手指在 $\textit{word}[n-1]$，另一根手指的位置不确定，枚举 $\textit{anotherFinger}$。
###py
# 预处理两个字母的距离
COLUMN = 6
get_dis = lambda a, b: abs(a // COLUMN - b // COLUMN) + abs(a % COLUMN - b % COLUMN)
dis = [[get_dis(i, j) for j in range(26)] for i in range(26)]
class Solution:
def minimumDistance(self, word: str) -> int:
word = [ord(ch) - ord('A') for ch in word] # 避免在 dfs 中频繁调用 ord
@cache # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
def dfs(i: int, another_finger: int) -> int:
if i < 0:
return 0
# 在 word[i+1] 的手指移到 word[i]
res1 = dfs(i - 1, another_finger) + dis[word[i + 1]][word[i]]
# 另一根手指移到 word[i]，原来在 word[i+1] 的手指变成 another_finger
res2 = dfs(i - 1, word[i + 1]) + dis[another_finger][word[i]]
return min(res1, res2)
n = len(word)
# 最后一定有一根手指在 word[-1]，另一根手指的位置不确定，枚举
return min(dfs(n - 2, another_finger) for another_finger in range(26))
###java
class Solution {
private static final int[][] dis = new int[26][26];
static {
// 预处理两个字母的距离
final int COLUMN = 6;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
dis[i][j] = Math.abs(i / COLUMN - j / COLUMN) + Math.abs(i % COLUMN - j % COLUMN);
}
}
}
public int minimumDistance(String word) {
char[] s = word.toCharArray();
int n = s.length;
int[][] memo = new int[n][26];
for (int[] row : memo) {
Arrays.fill(row, -1); // -1 表示没有计算过
}
int ans = Integer.MAX_VALUE;
// 最后一定有一根手指在 s[n-1]，另一根手指的位置不确定，枚举
for (int anotherFinger = 0; anotherFinger < 26; anotherFinger++) {
ans = Math.min(ans, dfs(n - 2, anotherFinger, s, memo));
}
return ans;
}
private int dfs(int i, int anotherFinger, char[] word, int[][] memo) {
if (i < 0) {
return 0;
}
if (memo[i][anotherFinger] != -1) { // 之前计算过
return memo[i][anotherFinger];
}
// 在 word[i+1] 的手指移到 word[i]
int w = word[i] - 'A';
int res1 = dfs(i - 1, anotherFinger, word, memo) + dis[word[i + 1] - 'A'][w];
// 另一根手指移到 word[i]，原来在 word[i+1] 的手指变成 anotherFinger
int res2 = dfs(i - 1, word[i + 1] - 'A', word, memo) + dis[anotherFinger][w];
int res = Math.min(res1, res2);
memo[i][anotherFinger] = res; // 记忆化
return res;
}
}
###cpp
int dis[26][26];
auto init = [] {
// 预处理两个字母的距离
constexpr int COLUMN = 6;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
dis[i][j] = abs(i / COLUMN - j / COLUMN) + abs(i % COLUMN - j % COLUMN);
}
}
return 0;
}();
class Solution {
public:
int minimumDistance(string word) {
int n = word.size();
vector memo(n, vector<int>(26, -1)); // -1 表示没有计算过
auto dfs = [&](this auto&& dfs, int i, int another_finger) -> int {
if (i < 0) {
return 0;
}
int& res = memo[i][another_finger]; // 注意这里是引用
if (res != -1) { // 之前计算过
return res;
}
// 在 word[i+1] 的手指移到 word[i]
int w = word[i] - 'A';
int res1 = dfs(i - 1, another_finger) + dis[word[i + 1] - 'A'][w];
// 另一根手指移到 word[i]，原来在 word[i+1] 的手指变成 another_finger
int res2 = dfs(i - 1, word[i + 1] - 'A') + dis[another_finger][w];
res = min(res1, res2);
return res;
};
int ans = INT_MAX;
// 最后一定有一根手指在 word[n-1]，另一根手指的位置不确定，枚举
for (int another_finger = 0; another_finger < 26; another_finger++) {
ans = min(ans, dfs(n - 2, another_finger));
}
return ans;
}
};
###go
var dis [26][26]int
func init() {
// 预处理两个字母的距离
const column = 6
for i := range 26 {
for j := range 26 {
dis[i][j] = abs(i/column-j/column) + abs(i%column-j%column)
}
}
}
func minimumDistance(word string) int {
n := len(word)
memo := make([][26]int, n)
var dfs func(int, byte) int
dfs = func(i int, anotherFinger byte) (res int) {
if i < 0 {
return 0
}
p := &memo[i][anotherFinger]
if *p != 0 { // 之前计算过
return *p - 1
}
defer func() { *p = res + 1 }() // 记忆化的时候加一，这样就无需初始化 memo 为 -1 了
// 手指 1 移到 word[i]
w := word[i] - 'A'
res1 := dfs(i-1, anotherFinger) + dis[word[i+1]-'A'][w]
// 手指 2 移到 word[i]
res2 := dfs(i-1, word[i+1]-'A') + dis[anotherFinger][w]
return min(res1, res2)
}
ans := math.MaxInt
// 最后一定有一根手指在 word[n-1]，另一根手指的位置不确定，枚举
for anotherFinger := range byte(26) {
ans = min(ans, dfs(n-2, anotherFinger))
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
不计入预处理的时间和空间。
我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。
具体来说，$f[i+1][\textit{anotherFinger}]$ 的定义和 $\textit{dfs}(i,\textit{anotherFinger})$ 的定义是一样的，都表示在一根手指位于字母 $\textit{word}[i+1]$，另一根手指位于字母 $\textit{anotherFinger}$ 的情况下，输入 $\textit{word}$ 的前缀 $[0,i]$ 的最小移动总距离。这里 $+1$ 是为了把 $\textit{dfs}(-1,\textit{anotherFinger})$ 这个状态也翻译过来，这样我们可以把 $f[0]$ 作为初始值。
相应的递推式（状态转移方程）也和 $\textit{dfs}$ 一样：
$$
f[i+1][\textit{anotherFinger}] = \min
\begin{cases}
f[i][\textit{anotherFinger}] + \textit{dis}[\textit{word}[i+1]][\textit{word}[i]] \
f[i][\textit{word}[i+1]] + \textit{dis}[\textit{anotherFinger}][\textit{word}[i]] \
\end{cases}
$$
初始值 $f[0][\textit{anotherFinger}]=0$，翻译自递归边界 $\textit{dfs}(-1, \textit{anotherFinger})$。
答案为 $f[n-1][\textit{anotherFinger}]$，翻译自递归入口 $\textit{dfs}(n-2, \textit{anotherFinger})$。
###py
# 预处理两个字母的距离
COLUMN = 6
get_dis = lambda a, b: abs(a // COLUMN - b // COLUMN) + abs(a % COLUMN - b % COLUMN)
dis = [[get_dis(i, j) for j in range(26)] for i in range(26)]
class Solution:
def minimumDistance(self, word: str) -> int:
f = [[0] * 26 for _ in word]
for i, (x, y) in enumerate(pairwise(word)):
x = ord(x) - ord('A')
y = ord(y) - ord('A')
for another_finger in range(26):
f[i + 1][another_finger] = min(f[i][another_finger] + dis[y][x], f[i][y] + dis[another_finger][x])
return min(f[-1])
###java
class Solution {
private static final int[][] dis = new int[26][26];
static {
// 预处理两个字母的距离
final int COLUMN = 6;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
dis[i][j] = Math.abs(i / COLUMN - j / COLUMN) + Math.abs(i % COLUMN - j % COLUMN);
}
}
}
public int minimumDistance(String word) {
char[] s = word.toCharArray();
int n = s.length;
int[][] f = new int[n][26];
for (int i = 0; i < n - 1; i++) {
int x = s[i] - 'A';
int y = s[i + 1] - 'A';
for (int anotherFinger = 0; anotherFinger < 26; anotherFinger++) {
f[i + 1][anotherFinger] = Math.min(f[i][anotherFinger] + dis[y][x], f[i][y] + dis[anotherFinger][x]);
}
}
int ans = Integer.MAX_VALUE;
for (int res : f[n - 1]) {
ans = Math.min(ans, res);
}
return ans;
}
}
###cpp
int dis[26][26];
auto init = [] {
// 预处理两个字母的距离
constexpr int COLUMN = 6;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
dis[i][j] = abs(i / COLUMN - j / COLUMN) + abs(i % COLUMN - j % COLUMN);
}
}
return 0;
}();
class Solution {
public:
int minimumDistance(string word) {
int n = word.size();
vector<array<int, 26>> f(n);
for (int i = 0; i < n - 1; i++) {
int x = word[i] - 'A', y = word[i + 1] - 'A';
for (int another_finger = 0; another_finger < 26; another_finger++) {
f[i + 1][another_finger] = min(f[i][another_finger] + dis[y][x], f[i][y] + dis[another_finger][x]);
}
}
return ranges::min(f[n - 1]);
}
};
###go
var dis [26][26]int
func init() {
// 预处理两个字母的距离
const column = 6
for i := range 26 {
for j := range 26 {
dis[i][j] = abs(i/column-j/column) + abs(i%column-j%column)
}
}
}
func minimumDistance(word string) int {
n := len(word)
f := make([][26]int, n)
for i := range n - 1 {
x, y := word[i]-'A', word[i+1]-'A'
for anotherFinger := range 26 {
f[i+1][anotherFinger] = min(f[i][anotherFinger]+dis[y][x], f[i][y]+dis[anotherFinger][x])
}
}
return slices.Min(f[n-1][:])
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
不计入预处理的时间和空间。
由于 $f[i+1]$ 只依赖 $f[i]$，那么 $f[i-1]$ 及其之前的数据就没用了。
例如计算 $f[2]$ 的时候，数组 $f[0]$ 不再使用了。
那么干脆把 $f[2]$ 填到 $f[0]$ 中，$f[3]$ 填到 $f[1]$ 中，$f[4]$ 填到 $f[0]$ 中，$f[5]$ 填到 $f[1]$ 中 …… 只用两个长为 $26$ 的数组滚动计算。
此外，由于 $\textit{dis}[x][y] = \textit{dis}[y][x]$，我们可以交换转移方程中的 $\textit{dis}$ 的两个维度，这样在同一个内层循环中只会访问 $\textit{dis}[x]$ 这一个数组。
###py
COLUMN = 6
get_dis = lambda a, b: abs(a // COLUMN - b // COLUMN) + abs(a % COLUMN - b % COLUMN)
dis = [[get_dis(i, j) for j in range(26)] for i in range(26)]
class Solution:
def minimumDistance(self, word: str) -> int:
f = [0] * 26
nf = [0] * 26
for x, y in pairwise(word):
x = ord(x) - ord('A')
y = ord(y) - ord('A')
dis_x = dis[x]
for another_finger in range(26):
nf[another_finger] = min(f[another_finger] + dis_x[y], f[y] + dis_x[another_finger])
f, nf = nf, f
return min(f)
###java
class Solution {
private static final int[][] dis = new int[26][26];
static {
final int COLUMN = 6;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
dis[i][j] = Math.abs(i / COLUMN - j / COLUMN) + Math.abs(i % COLUMN - j % COLUMN);
}
}
}
public int minimumDistance(String word) {
char[] s = word.toCharArray();
int[] f = new int[26];
int[] nf = new int[26];
for (int i = 0; i < s.length - 1; i++) {
int x = s[i] - 'A';
int y = s[i + 1] - 'A';
for (int anotherFinger = 0; anotherFinger < 26; anotherFinger++) {
nf[anotherFinger] = Math.min(f[anotherFinger] + dis[x][y], f[y] + dis[x][anotherFinger]);
}
int[] tmp = f;
f = nf;
nf = tmp;
}
int ans = Integer.MAX_VALUE;
for (int res : f) {
ans = Math.min(ans, res);
}
return ans;
}
}
###cpp
int dis[26][26];
auto init = [] {
constexpr int COLUMN = 6;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
dis[i][j] = abs(i / COLUMN - j / COLUMN) + abs(i % COLUMN - j % COLUMN);
}
}
return 0;
}();
class Solution {
public:
int minimumDistance(string word) {
int n = word.size();
int f[26]{}, nf[26];
for (int i = 0; i < n - 1; i++) {
int x = word[i] - 'A', y = word[i + 1] - 'A';
for (int another_finger = 0; another_finger < 26; another_finger++) {
nf[another_finger] = min(f[another_finger] + dis[x][y], f[y] + dis[x][another_finger]);
}
swap(f, nf);
}
return ranges::min(f);
}
};
###go
var dis [26][26]int
func init() {
const column = 6
for i := range 26 {
for j := range 26 {
dis[i][j] = abs(i/column-j/column) + abs(i%column-j%column)
}
}
}
func minimumDistance(word string) int {
var f, nf [26]int
for i := range len(word) - 1 {
x, y := word[i]-'A', word[i+1]-'A'
for anotherFinger := range 26 {
nf[anotherFinger] = min(f[anotherFinger]+dis[x][y], f[y]+dis[x][anotherFinger])
}
f, nf = nf, f
}
return slices.Min(f[:])
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
不计入预处理的时间和空间。
见下面动态规划题单的「§7.6 多维 DP」。
欢迎关注 B站@灵茶山艾府
我们用 dp[i][l][r] 表示在输入了字符串 word 的第 i 个字母后，左手的位置为 l，右手的位置为 r，达到该状态的最小移动距离。这里的位置为指向的字母编号，例如 A 对应 0，B 对应 1，以此类推，而非字母在键盘上的位置。这样做的好处是将字母的位置映射成一个整数而非二维的坐标，使得我们更加方便地进行状态转移。
那么如何进行状态转移呢？我们首先需要看出一个非常重要的性质：对于状态 dp[i][l][r]，要么 word[i] == l，要么 word[i] == r，即在输入了第 i 个字母后，左手和右手中至少有一个在 word[i] 的位置。我们可以根据这两种情况，分别进行状态转移：
当 word[i] == l 时，左手在 word[i] 的位置。我们需要考虑在输入字符串 word 的第 i - 1 个字母时，是左手还是右手在 word[i - 1] 的位置：
如果左手在 word[i - 1] 的位置，那么在输入第 i 个字母时，左手从 word[i - 1] 移动至 word[i]，状态转移方程为：
dp[i][l = word[i]][r] = dp[i - 1][l0 = word[i - 1]][r] + dist(word[i - 1], word[i])
如果右手在 word[i - 1] 的位置，那么由于第 i 个字母使用了左手，右手就没有移动，即 word[i - 1] == r。同时，在输入 word[i1] 之前的左手位置也无关紧要，可以为任意的 l0，状态转移方程为：
dp[i][l = word[i]][r = word[i - 1]] = dp[i - 1][l0][r = word[i - 1]] + dist(l0, word[i])
当 word[i] == r 时，右手在 word[i] 的位置。我们需要考虑在输入字符串 word 的第 i - 1 个字母时，是右手还是左手在 word[i - 1] 的位置：
如果右手在 word[i - 1] 的位置，那么在输入第 i 个字母时，右手从 word[i - 1] 移动至 word[i]，状态转移方程为：
dp[i][l][r = word[i]] = dp[i - 1][l][r0 = word[i - 1]] + dist(word[i - 1], word[i])
如果左手在 word[i - 1] 的位置，那么由于第 i 个字母使用了右手，左手就没有移动，即 word[i - 1] == l。同时，在输入 word[i] 之前的右手位置也无关紧要，可以为任意的 r0，状态转移方程为：
dp[i][l = word[i - 1]][r = word[i]] = dp[i - 1][l = word[i - 1]][r0] + dist(r0, word[i])
对于每一个状态 dp[i][l][r]，我们取它所有转移中的最小值，即为输入了字符串 word 的第 i 个字母后，左手的位置为 l，右手的位置为 r，达到该状态的最小移动距离。
在这个动态规划中，我们还需要考虑不合法的状态以及边界状态。对于某一个不合法的状态，如果用它来进行状态转移，可能会使得 dp[i][l][r] 取到一个更小且不合法的值。因此，我们一般会给所有不合法的状态赋予一个非常大的值（例如 C++ 中的整数最大值 INT_MAX），这样即使用它来进行状态转移，也会因为本身值非常大的缘故，对最优解没有任何影响。在考虑边界状态时，由于题目中规定两根手指的起始位置是零代价的，因此对于字符串中的第 0 个字母 word[0]，输入它的最小移动距离为 0。此时要么左手的位置为 word[0]，要么右手的位置为 word[0]，因此我们可以将所有的 dp[0][l = word[0]][r] 以及 dp[0][l][r = word[0]] 作为边界状态，它们的值为 0。
###C++
class Solution {
public:
int getDistance(int p, int q) {
int x1 = p / 6, y1 = p % 6;
int x2 = q / 6, y2 = q % 6;
return abs(x1 - x2) + abs(y1 - y2);
}
int minimumDistance(string word) {
int n = word.size();
int dp[n][26][26];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
fill(dp[i][j], dp[i][j] + 26, INT_MAX >> 1);
}
}
for (int i = 0; i < 26; ++i) {
dp[0][i][word[0] - 'A'] = dp[0][word[0] - 'A'][i] = 0;
}
for (int i = 1; i < n; ++i) {
int cur = word[i] - 'A';
int prev = word[i - 1] - 'A';
int d = getDistance(prev, cur);
for (int j = 0; j < 26; ++j) {
dp[i][cur][j] = min(dp[i][cur][j], dp[i - 1][prev][j] + d);
dp[i][j][cur] = min(dp[i][j][cur], dp[i - 1][j][prev] + d);
if (prev == j) {
for (int k = 0; k < 26; ++k) {
int d0 = getDistance(k, cur);
dp[i][cur][j] = min(dp[i][cur][j], dp[i - 1][k][j] + d0);
dp[i][j][cur] = min(dp[i][j][cur], dp[i - 1][j][k] + d0);
}
}
}
}
int ans = INT_MAX >> 1;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
ans = min(ans, dp[n - 1][i][j]);
}
}
return ans;
}
};
###Python
class Solution:
def minimumDistance(self, word: str) -> int:
n = len(word)
BIG = 2**30
dp = [[[BIG] * 26 for x in range(26)] for y in range(n)]
for i in range(26):
dp[0][i][ord(word[0]) - 65] = 0
dp[0][ord(word[0]) - 65][i] = 0
def getDistance(p, q):
x1, y1 = p // 6, p % 6
x2, y2 = q // 6, q % 6
return abs(x1 - x2) + abs(y1 - y2)
for i in range(1, n):
cur, prev = ord(word[i]) - 65, ord(word[i - 1]) - 65
d = getDistance(prev, cur)
for j in range(26):
dp[i][cur][j] = min(dp[i][cur][j], dp[i - 1][prev][j] + d)
dp[i][j][cur] = min(dp[i][j][cur], dp[i - 1][j][prev] + d)
if prev == j:
for k in range(26):
d0 = getDistance(k, cur)
dp[i][cur][j] = min(dp[i][cur][j], dp[i - 1][k][j] + d0)
dp[i][j][cur] = min(dp[i][j][cur], dp[i - 1][j][k] + d0)
ans = min(min(dp[n - 1][x]) for x in range(26))
return ans
###Java
class Solution {
private int getDistance(int p, int q) {
int x1 = p / 6, y1 = p % 6;
int x2 = q / 6, y2 = q % 6;
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
public int minimumDistance(String word) {
int n = word.length();
int[][][] dp = new int[n][26][26];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
for (int k = 0; k < 26; ++k) {
dp[i][j][k] = Integer.MAX_VALUE / 2;
}
}
}
for (int i = 0; i < 26; ++i) {
dp[0][i][word.charAt(0) - 'A'] = 0;
dp[0][word.charAt(0) - 'A'][i] = 0;
}
for (int i = 1; i < n; ++i) {
int cur = word.charAt(i) - 'A';
int prev = word.charAt(i - 1) - 'A';
int d = getDistance(prev, cur);
for (int j = 0; j < 26; ++j) {
dp[i][cur][j] = Math.min(dp[i][cur][j], dp[i - 1][prev][j] + d);
dp[i][j][cur] = Math.min(dp[i][j][cur], dp[i - 1][j][prev] + d);
if (prev == j) {
for (int k = 0; k < 26; ++k) {
int d0 = getDistance(k, cur);
dp[i][cur][j] = Math.min(dp[i][cur][j], dp[i - 1][k][j] + d0);
dp[i][j][cur] = Math.min(dp[i][j][cur], dp[i - 1][j][k] + d0);
}
}
}
}
int ans = Integer.MAX_VALUE / 2;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
ans = Math.min(ans, dp[n - 1][i][j]);
}
}
return ans;
}
}
###C#
public class Solution {
private int GetDistance(int p, int q) {
int x1 = p / 6, y1 = p % 6;
int x2 = q / 6, y2 = q % 6;
return Math.Abs(x1 - x2) + Math.Abs(y1 - y2);
}
public int MinimumDistance(string word) {
int n = word.Length;
int[,,] dp = new int[n, 26, 26];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
for (int k = 0; k < 26; ++k) {
dp[i, j, k] = int.MaxValue / 2;
}
}
}
for (int i = 0; i < 26; ++i) {
dp[0, i, word[0] - 'A'] = 0;
dp[0, word[0] - 'A', i] = 0;
}
for (int i = 1; i < n; ++i) {
int cur = word[i] - 'A';
int prev = word[i - 1] - 'A';
int d = GetDistance(prev, cur);
for (int j = 0; j < 26; ++j) {
dp[i, cur, j] = Math.Min(dp[i, cur, j], dp[i - 1, prev, j] + d);
dp[i, j, cur] = Math.Min(dp[i, j, cur], dp[i - 1, j, prev] + d);
if (prev == j) {
for (int k = 0; k < 26; ++k) {
int d0 = GetDistance(k, cur);
dp[i, cur, j] = Math.Min(dp[i, cur, j], dp[i - 1, k, j] + d0);
dp[i, j, cur] = Math.Min(dp[i, j, cur], dp[i - 1, j, k] + d0);
}
}
}
}
int ans = int.MaxValue / 2;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
ans = Math.Min(ans, dp[n - 1, i, j]);
}
}
return ans;
}
}
###Go
func getDistance(p, q int) int {
x1, y1 := p/6, p%6
x2, y2 := q/6, q%6
return abs(x1 - x2) + abs(y1 - y2)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func minimumDistance(word string) int {
n := len(word)
dp := make([][26][26]int, n)
for i := 0; i < n; i++ {
for j := 0; j < 26; j++ {
for k := 0; k < 26; k++ {
dp[i][j][k] = 1 << 30
}
}
}
firstChar := int(word[0] - 'A')
for i := 0; i < 26; i++ {
dp[0][i][firstChar] = 0
dp[0][firstChar][i] = 0
}
for i := 1; i < n; i++ {
cur := int(word[i] - 'A')
prev := int(word[i-1] - 'A')
d := getDistance(prev, cur)
for j := 0; j < 26; j++ {
dp[i][cur][j] = min(dp[i][cur][j], dp[i-1][prev][j]+d)
dp[i][j][cur] = min(dp[i][j][cur], dp[i-1][j][prev]+d)
if prev == j {
for k := 0; k < 26; k++ {
d0 := getDistance(k, cur)
dp[i][cur][j] = min(dp[i][cur][j], dp[i-1][k][j]+d0)
dp[i][j][cur] = min(dp[i][j][cur], dp[i-1][j][k]+d0)
}
}
}
}
ans := 1 << 30
for i := 0; i < 26; i++ {
for j := 0; j < 26; j++ {
ans = min(ans, dp[n-1][i][j])
}
}
return ans
}
###C
int getDistance(int p, int q) {
int x1 = p / 6, y1 = p % 6;
int x2 = q / 6, y2 = q % 6;
return abs(x1 - x2) + abs(y1 - y2);
}
int minimumDistance(char* word) {
int n = strlen(word);
int*** dp = (int***)malloc(n * sizeof(int**));
for (int i = 0; i < n; ++i) {
dp[i] = (int**)malloc(26 * sizeof(int*));
for (int j = 0; j < 26; ++j) {
dp[i][j] = (int*)malloc(26 * sizeof(int));
for (int k = 0; k < 26; ++k) {
dp[i][j][k] = INT_MAX / 2;
}
}
}
for (int i = 0; i < 26; ++i) {
dp[0][i][word[0] - 'A'] = 0;
dp[0][word[0] - 'A'][i] = 0;
}
for (int i = 1; i < n; ++i) {
int cur = word[i] - 'A';
int prev = word[i - 1] - 'A';
int d = getDistance(prev, cur);
for (int j = 0; j < 26; ++j) {
dp[i][cur][j] = fmin(dp[i][cur][j], dp[i - 1][prev][j] + d);
dp[i][j][cur] = fmin(dp[i][j][cur], dp[i - 1][j][prev] + d);
if (prev == j) {
for (int k = 0; k < 26; ++k) {
int d0 = getDistance(k, cur);
dp[i][cur][j] = fmin(dp[i][cur][j], dp[i - 1][k][j] + d0);
dp[i][j][cur] = fmin(dp[i][j][cur], dp[i - 1][j][k] + d0);
}
}
}
}
int ans = INT_MAX / 2;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
if (ans > dp[n - 1][i][j]) {
ans = dp[n - 1][i][j];
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
free(dp[i][j]);
}
free(dp[i]);
}
free(dp);
return ans;
}
###JavaScript
var minimumDistance = function(word) {
const n = word.length;
const getDistance = (p, q) => {
const x1 = Math.floor(p / 6), y1 = p % 6;
const x2 = Math.floor(q / 6), y2 = q % 6;
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};
const dp = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(26);
for (let j = 0; j < 26; j++) {
dp[i][j] = new Array(26).fill(Math.floor(Number.MAX_SAFE_INTEGER / 2));
}
}
const firstChar = word.charCodeAt(0) - 65;
for (let i = 0; i < 26; i++) {
dp[0][i][firstChar] = 0;
dp[0][firstChar][i] = 0;
}
for (let i = 1; i < n; i++) {
const cur = word.charCodeAt(i) - 65;
const prev = word.charCodeAt(i - 1) - 65;
const d = getDistance(prev, cur);
for (let j = 0; j < 26; j++) {
dp[i][cur][j] = Math.min(dp[i][cur][j], dp[i - 1][prev][j] + d);
dp[i][j][cur] = Math.min(dp[i][j][cur], dp[i - 1][j][prev] + d);
if (prev === j) {
for (let k = 0; k < 26; k++) {
const d0 = getDistance(k, cur);
dp[i][cur][j] = Math.min(dp[i][cur][j], dp[i - 1][k][j] + d0);
dp[i][j][cur] = Math.min(dp[i][j][cur], dp[i - 1][j][k] + d0);
}
}
}
}
let ans = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < 26; i++) {
for (let j = 0; j < 26; j++) {
ans = Math.min(ans, dp[n - 1][i][j]);
}
}
return ans;
};
###TypeScript
function minimumDistance(word: string): number {
const n = word.length;
const getDistance = (p: number, q: number): number => {
const x1 = Math.floor(p / 6), y1 = p % 6;
const x2 = Math.floor(q / 6), y2 = q % 6;
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};
const dp: number[][][] = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(26);
for (let j = 0; j < 26; j++) {
dp[i][j] = new Array(26).fill(Math.floor(Number.MAX_SAFE_INTEGER / 2));
}
}
const firstChar = word.charCodeAt(0) - 65;
for (let i = 0; i < 26; i++) {
dp[0][i][firstChar] = 0;
dp[0][firstChar][i] = 0;
}
for (let i = 1; i < n; i++) {
const cur = word.charCodeAt(i) - 65;
const prev = word.charCodeAt(i - 1) - 65;
const d = getDistance(prev, cur);
for (let j = 0; j < 26; j++) {
dp[i][cur][j] = Math.min(dp[i][cur][j], dp[i - 1][prev][j] + d);
dp[i][j][cur] = Math.min(dp[i][j][cur], dp[i - 1][j][prev] + d);
if (prev === j) {
for (let k = 0; k < 26; k++) {
const d0 = getDistance(k, cur);
dp[i][cur][j] = Math.min(dp[i][cur][j], dp[i - 1][k][j] + d0);
dp[i][j][cur] = Math.min(dp[i][j][cur], dp[i - 1][j][k] + d0);
}
}
}
}
let ans = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < 26; i++) {
for (let j = 0; j < 26; j++) {
ans = Math.min(ans, dp[n - 1][i][j]);
}
}
return ans;
}
###Rust
impl Solution {
fn get_distance(p: i32, q: i32) -> i32 {
let x1 = p / 6;
let y1 = p % 6;
let x2 = q / 6;
let y2 = q % 6;
(x1 - x2).abs() + (y1 - y2).abs()
}
pub fn minimum_distance(word: String) -> i32 {
let n = word.len();
let word_chars: Vec<char> = word.chars().collect();
let mut dp = vec![vec![vec![i32::MAX >> 1; 26]; 26]; n];
let first_char = (word_chars[0] as u8 - b'A') as usize;
for i in 0..26 {
dp[0][i][first_char] = 0;
dp[0][first_char][i] = 0;
}
for i in 1..n {
let cur = (word_chars[i] as u8 - b'A') as i32;
let prev = (word_chars[i - 1] as u8 - b'A') as i32;
let d = Self::get_distance(prev, cur);
for j in 0..26 {
let j_i32 = j as i32;
dp[i][cur as usize][j] = dp[i][cur as usize][j].min(
dp[i - 1][prev as usize][j].saturating_add(d)
);
dp[i][j][cur as usize] = dp[i][j][cur as usize].min(
dp[i - 1][j][prev as usize].saturating_add(d)
);
if prev == j_i32 {
for k in 0..26 {
let d0 = Self::get_distance(k as i32, cur);
dp[i][cur as usize][j] = dp[i][cur as usize][j].min(
dp[i - 1][k][j].saturating_add(d0)
);
dp[i][j][cur as usize] = dp[i][j][cur as usize].min(
dp[i - 1][j][k].saturating_add(d0)
);
}
}
}
}
let mut ans = i32::MAX >> 1;
for i in 0..26 {
for j in 0..26 {
ans = ans.min(dp[n - 1][i][j]);
}
}
ans
}
}
复杂度分析
时间复杂度：$O(|\Sigma|N)$，其中 $N$ 是字符串 word 的长度，$|\Sigma|$ 是可能出现的字母数量，在本题中 $|\Sigma| = 26$。对于状态 dp[i][l][r]，枚举 i 需要的时间复杂度为 $O(N)$，在此之后，如果 word[i] == l，根据上面的状态转移方程：
如果左手在 word[i - 1] 的位置，那么单次状态转移的时间复杂度为 $O(1)$，需要对所有的 r 都进行转移，总时间复杂度为 $O(|\Sigma|)$；
如果右手在 word[i - 1] 的位置，那么 r == word[i - 1]。虽然我们要枚举 l0，但是合法的 r 只有一个，因此总时间复杂度也为 $O(|\Sigma|)$。
如果 word[i] == r，分析的过程相同，在此不再赘述。这样总时间复杂度即为 $O(|\Sigma|N)$。
空间复杂度：$O(|\Sigma|^2 N)$。
在方法一中，我们提到了一条重要的性质：对于状态 dp[i][l][r]，要么 word[i] == l，要么 word[i] == r，即在输入了第 i 个字母后，左手和右手中至少有一个在 word[i] 的位置。那么对于每一个 i，我们其实只需要存储 $2|\Sigma|$ 而不是 $|\Sigma|^2$ 个状态。例如我们可以用 dp[i][op][rest] 表示状态，其中 op 的值只能为 0 或 1，op == 0 表示左手在 word[i] 的位置，op == 1 表示右手在 word[i] 的位置，而 rest 表示不在 word[i] 位置的另一只手的位置。这样我们在状态转移方程几乎不变的前提下，减少了动态规划需要的空间。
那么我们是否还可以继续进行优化呢？我们可以发现，在方法一中，状态转移方程具有高度对称性，那么我们可以断定，dp[i][op = 0][rest] 和 dp[i][op = 1][rest] 的值一定是相等的。这是因为 dp[i][op = 0][rest] 表示左手在 word[i] 的位置且右手在 rest 的位置，如果我们将左右手互换，那么我们同样可以使用 dp[i][op = 0][rest] 的移动距离使得右手在 word[i] 的位置且左手在 rest 的位置，而这恰好就是 dp[i][op = 1][rest]。
因此我们可以直接使用 dp[i][rest] 进行状态转移，其表示一只手在 word[i] 的位置，另一只手在 rest 的位置的最小移动距离。我们并不需要关心具体哪只手在 word[i] 的位置，因为两只手是完全对称的。这样以来，我们将三维的动态规划优化至了二维，大大减少了空间的使用。
###C++
class Solution {
public:
int getDistance(int p, int q) {
int x1 = p / 6, y1 = p % 6;
int x2 = q / 6, y2 = q % 6;
return abs(x1 - x2) + abs(y1 - y2);
}
int minimumDistance(string word) {
int n = word.size();
vector<vector<int>> dp(n, vector<int>(26, INT_MAX >> 1));
fill(dp[0].begin(), dp[0].end(), 0);
for (int i = 1; i < n; ++i) {
int cur = word[i] - 'A';
int prev = word[i - 1] - 'A';
int d = getDistance(prev, cur);
for (int j = 0; j < 26; ++j) {
dp[i][j] = min(dp[i][j], dp[i - 1][j] + d);
if (prev == j) {
for (int k = 0; k < 26; ++k) {
int d0 = getDistance(k, cur);
dp[i][j] = min(dp[i][j], dp[i - 1][k] + d0);
}
}
}
}
int ans = *min_element(dp[n - 1].begin(), dp[n - 1].end());
return ans;
}
};
###Python
class Solution:
def minimumDistance(self, word: str) -> int:
n = len(word)
BIG = 2**30
dp = [[0] * 26] + [[BIG] * 26 for _ in range(n - 1)]
def getDistance(p, q):
x1, y1 = p // 6, p % 6
x2, y2 = q // 6, q % 6
return abs(x1 - x2) + abs(y1 - y2)
for i in range(1, n):
cur, prev = ord(word[i]) - 65, ord(word[i - 1]) - 65
d = getDistance(prev, cur)
for j in range(26):
dp[i][j] = min(dp[i][j], dp[i - 1][j] + d)
if prev == j:
for k in range(26):
d0 = getDistance(k, cur)
dp[i][j] = min(dp[i][j], dp[i - 1][k] + d0)
ans = min(dp[n - 1])
return ans
###Java
class Solution {
private int getDistance(int p, int q) {
int x1 = p / 6, y1 = p % 6;
int x2 = q / 6, y2 = q % 6;
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
public int minimumDistance(String word) {
int n = word.length();
int[][] dp = new int[n][26];
for (int i = 0; i < n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
}
Arrays.fill(dp[0], 0);
for (int i = 1; i < n; i++) {
int cur = word.charAt(i) - 'A';
int prev = word.charAt(i - 1) - 'A';
int d = getDistance(prev, cur);
for (int j = 0; j < 26; j++) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + d);
if (prev == j) {
for (int k = 0; k < 26; k++) {
int d0 = getDistance(k, cur);
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + d0);
}
}
}
}
int ans = Integer.MAX_VALUE / 2;
for (int value : dp[n - 1]) {
ans = Math.min(ans, value);
}
return ans;
}
}
###C#
public class Solution {
private int GetDistance(int p, int q) {
int x1 = p / 6, y1 = p % 6;
int x2 = q / 6, y2 = q % 6;
return Math.Abs(x1 - x2) + Math.Abs(y1 - y2);
}
public int MinimumDistance(string word) {
int n = word.Length;
int[,] dp = new int[n, 26];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 26; j++) {
dp[i, j] = int.MaxValue / 2;
}
}
for (int j = 0; j < 26; j++) {
dp[0, j] = 0;
}
for (int i = 1; i < n; i++) {
int cur = word[i] - 'A';
int prev = word[i - 1] - 'A';
int d = GetDistance(prev, cur);
for (int j = 0; j < 26; j++) {
dp[i, j] = Math.Min(dp[i, j], dp[i - 1, j] + d);
if (prev == j) {
for (int k = 0; k < 26; k++) {
int d0 = GetDistance(k, cur);
dp[i, j] = Math.Min(dp[i, j], dp[i - 1, k] + d0);
}
}
}
}
int ans = int.MaxValue / 2;
for (int j = 0; j < 26; j++) {
ans = Math.Min(ans, dp[n - 1, j]);
}
return ans;
}
}
###Go
func getDistance(p, q int) int {
x1, y1 := p / 6, p % 6
x2, y2 := q / 6, q % 6
return abs(x1 - x2) + abs(y1 - y2)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func minimumDistance(word string) int {
n := len(word)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, 26)
for j := range dp[i] {
dp[i][j] = 1 << 30
}
}
for j := 0; j < 26; j++ {
dp[0][j] = 0
}
for i := 1; i < n; i++ {
cur := int(word[i] - 'A')
prev := int(word[i-1] - 'A')
d := getDistance(prev, cur)
for j := 0; j < 26; j++ {
dp[i][j] = min(dp[i][j], dp[i-1][j]+d)
if prev == j {
for k := 0; k < 26; k++ {
d0 := getDistance(k, cur)
dp[i][j] = min(dp[i][j], dp[i-1][k]+d0)
}
}
}
}
ans := 1 << 30
for j := 0; j < 26; j++ {
ans = min(ans, dp[n-1][j])
}
return ans
}
###C
int getDistance(int p, int q) {
int x1 = p / 6, y1 = p % 6;
int x2 = q / 6, y2 = q % 6;
return abs(x1 - x2) + abs(y1 - y2);
}
int minimumDistance(char* word) {
int n = strlen(word);
int** dp = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
dp[i] = (int*)malloc(26 * sizeof(int));
for (int j = 0; j < 26; j++) {
dp[i][j] = INT_MAX / 2;
}
}
for (int j = 0; j < 26; j++) {
dp[0][j] = 0;
}
for (int i = 1; i < n; i++) {
int cur = word[i] - 'A';
int prev = word[i - 1] - 'A';
int d = getDistance(prev, cur);
for (int j = 0; j < 26; j++) {
dp[i][j] = fmin(dp[i][j], dp[i - 1][j] + d);
if (prev == j) {
for (int k = 0; k < 26; k++) {
int d0 = getDistance(k, cur);
dp[i][j] = fmin(dp[i][j], dp[i - 1][k] + d0);
}
}
}
}
int ans = INT_MAX / 2;
for (int j = 0; j < 26; j++) {
if (ans > dp[n - 1][j]) {
ans = dp[n - 1][j];
}
}
for (int i = 0; i < n; i++) {
free(dp[i]);
}
free(dp);
return ans;
}
###JavaScript
var minimumDistance = function(word) {
const n = word.length;
const getDistance = (p, q) => {
const x1 = Math.floor(p / 6), y1 = p % 6;
const x2 = Math.floor(q / 6), y2 = q % 6;
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};
const dp = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(26).fill(Math.floor(Number.MAX_SAFE_INTEGER / 2));
}
for (let j = 0; j < 26; j++) {
dp[0][j] = 0;
}
for (let i = 1; i < n; i++) {
const cur = word.charCodeAt(i) - 65;
const prev = word.charCodeAt(i - 1) - 65;
const d = getDistance(prev, cur);
for (let j = 0; j < 26; j++) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + d);
if (prev === j) {
for (let k = 0; k < 26; k++) {
const d0 = getDistance(k, cur);
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + d0);
}
}
}
}
let ans = Math.floor(Number.MAX_SAFE_INTEGER / 2);
for (let j = 0; j < 26; j++) {
ans = Math.min(ans, dp[n - 1][j]);
}
return ans;
};
###TypeScript
function minimumDistance(word: string): number {
const n = word.length;
const getDistance = (p: number, q: number): number => {
const x1 = Math.floor(p / 6), y1 = p % 6;
const x2 = Math.floor(q / 6), y2 = q % 6;
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};
const dp: number[][] = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(26).fill(Math.floor(Number.MAX_SAFE_INTEGER / 2));
}
for (let j = 0; j < 26; j++) {
dp[0][j] = 0;
}
for (let i = 1; i < n; i++) {
const cur = word.charCodeAt(i) - 65;
const prev = word.charCodeAt(i - 1) - 65;
const d = getDistance(prev, cur);
for (let j = 0; j < 26; j++) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + d);
if (prev === j) {
for (let k = 0; k < 26; k++) {
const d0 = getDistance(k, cur);
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + d0);
}
}
}
}
let ans = Math.floor(Number.MAX_SAFE_INTEGER / 2);
for (let j = 0; j < 26; j++) {
ans = Math.min(ans, dp[n - 1][j]);
}
return ans;
}
###Rust
impl Solution {
fn get_distance(p: i32, q: i32) -> i32 {
let x1 = p / 6;
let y1 = p % 6;
let x2 = q / 6;
let y2 = q % 6;
(x1 - x2).abs() + (y1 - y2).abs()
}
pub fn minimum_distance(word: String) -> i32 {
let n = word.len();
let word_bytes = word.as_bytes();
let mut dp = vec![vec![i32::MAX >> 1; 26]; n];
for j in 0..26 {
dp[0][j] = 0;
}
for i in 1..n {
let cur = (word_bytes[i] - b'A') as i32;
let prev = (word_bytes[i - 1] - b'A') as i32;
let d = Self::get_distance(prev, cur);
for j in 0..26 {
let j_i32 = j as i32;
dp[i][j] = dp[i][j].min(dp[i - 1][j].saturating_add(d));
if prev == j_i32 {
for k in 0..26 {
let d0 = Self::get_distance(k as i32, cur);
dp[i][j] = dp[i][j].min(dp[i - 1][k].saturating_add(d0));
}
}
}
}
let mut ans = i32::MAX >> 1;
for j in 0..26 {
ans = ans.min(dp[n - 1][j]);
}
ans
}
}
复杂度分析
时间复杂度：$O(|\Sigma|N)$。
空间复杂度：$O(|\Sigma|N)$。
我们将左指和右指所在的键位组成，看成一个状态。每次输入一个字母时，则其中一个手指会进行移动，移动的过程即是状态转移的过程。并且由于字母输入的顺序是固定的，每一个字母都可以看成一个阶段，字母不断输入的过程即是阶段的递增，例如第一个字母为第一个阶段，第二个字母为第二个阶段，后面以此类推。
因此，我们需要一个三维的状态来表示整个动态规划的过程，包括当前考虑的字母下标，左指的键位，右指的键位。
二指组成形成的状态：
三维状态：
接下来，让我们思考状态如何进行转移。假设字符串为 CAKE，并且此时阶段为 1，即当前考虑字母是 A。在这个阶段下，左右指会存在一种现象，要么左指为 A ，要么右指为 A，此时才能输入字母 A。
对于左指为 A，表示我们通过移动左指来到达这个阶段，而右指是没有移动的。总结来说，这个阶段下，左指会变成 A，右指不变。因此，我们需要遍历上一个阶段左指和右指的所有情况，并且转移到下一个阶段时，只移动左指（dp[1][A][R] = Math.min(dp[1][A][R], dp[0][L][R] + move(L, A))）。
注意观察，如果上一个阶段右指为 R，此时这个阶段右指也必须保持不变，同样为 R。
对于右指为 A 的情况同理。
###java
class Solution {
public int minimumDistance(String word) {
// 初始化
int[][][] dp = new int[301][26][26];
for (int i = 1; i <= 300; i++) {
for (int j = 0; j < 26; j++) {
Arrays.fill(dp[i][j], Integer.MAX_VALUE);
}
}
int ans = Integer.MAX_VALUE;
char[] ca = word.toCharArray();
// 遍历每个字母
for (int i = 1; i <= word.length(); i++) {
int v = ca[i - 1] - 'A';
// 遍历上一个阶段左指键位
for (int l = 0; l < 26; l++) {
// 遍历上一个阶段右指键位
for (int r = 0; r < 26; r++) {
// 判断上一个阶段的状态是否存在
if (dp[i - 1][l][r] != Integer.MAX_VALUE) {
// 移动左指
dp[i][v][r] = Math.min(dp[i][v][r], dp[i - 1][l][r] + help(l, v));
// 移动右指
dp[i][l][v] = Math.min(dp[i][l][v], dp[i - 1][l][r] + help(r, v));
}
if (i == word.length()) {
ans = Math.min(ans, dp[i][v][r]);
ans = Math.min(ans, dp[i][l][v]);
}
}
}
}
return ans;
}
// 计算距离
public int help(int a, int b) {
int x = a / 6, y = a % 6;
int x2 = b / 6, y2 = b % 6;
return (int)(Math.abs(x - x2)) + (int)(Math.abs(y - y2));
}
}
word 的长度。word 的长度。由于每个阶段只和上个阶段相关，我们可以使用滚动数组思想，循环利用数组，例如 i % 2 代表当前阶段，(i - 1) % 2 代表上一个阶段。
值得注意的是，每次我们计算出新数组后dp[i % 2]，需要重新初始化另外一个数组dp[(i - 1) % 2]，读者可尝试注释相关代码， 观察结果。
###java
class Solution {
public int minimumDistance(String word) {
// 初始化
int[][][] dp = new int[2][26][26];
for (int i = 0; i < 26; i++) {
Arrays.fill(dp[1][i], Integer.MAX_VALUE);
}
int ans = Integer.MAX_VALUE;
char[] ca = word.toCharArray();
// 遍历每个字母
for (int i = 1; i <= word.length(); i++) {
int v = ca[i - 1] - 'A';
// 遍历上一个阶段左指键位
for (int l = 0; l < 26; l++) {
// 遍历上一个阶段右指键位
for (int r = 0; r < 26; r++) {
// 判断上一个阶段的状态是否存在
if (dp[(i - 1) % 2][l][r] == Integer.MAX_VALUE) {
continue;
}
if (dp[(i - 1) % 2][l][r] != Integer.MAX_VALUE) {
// 移动左指
dp[i % 2][v][r] = Math.min(dp[i % 2][v][r], dp[(i - 1) % 2][l][r] + help(l, v));
// 移动右指
dp[i % 2][l][v] = Math.min(dp[i % 2][l][v], dp[(i - 1) % 2][l][r] + help(r, v));
}
if (i == word.length()) {
ans = Math.min(ans, dp[i % 2][v][r]);
ans = Math.min(ans, dp[i % 2][l][v]);
}
}
}
// 重新初始化另外一个数组
for (int l = 0; l < 26; l++) {
for (int r = 0; r < 26; r++) {
dp[(i - 1) % 2][l][r] = Integer.MAX_VALUE;
}
}
}
return ans;
}
// 计算距离
public int help(int a, int b) {
int x = a / 6, y = a % 6;
int x2 = b / 6, y2 = b % 6;
return (int)(Math.abs(x - x2)) + (int)(Math.abs(y - y2));
}
}
word 的长度。我们再重新观察一下这三个维度信息，分别是：字母下标，左指的键位，右指的键位。由于每次需要按下一个字母，左指键位或者右指键位必然有一个是这个字母的键位，因此字母下标也隐含着一个指头的键位信息，使用三个维度显然会有冗余，我们可以重新设计一种新的状态：字母下标（可以代表第一个指头键位），另外一个指头的键位。
每次按下一个字母时，要么是字母下标所在的指头（第一个指头）移动，要么是另外一个指头移动。
第一个指头移动的状态转移图如下：
dp[1][r] = Math.min(dp[1][r], dp[0][r] + move(word[0], word[1]))另外一个指头移动的状态转移图如下：
dp[1][word[0]] = Math.min(dp[1][word[0]], dp[0][r] + move(r, word[1]))###java
class Solution {
public int minimumDistance(String word) {
// 初始化
int len = word.length();
int ans = Integer.MAX_VALUE;
char[] ca = word.toCharArray();
// 第一个字母的初始值为 0，从第二个字母开始考虑。
int[][] dp = new int[2][26];
Arrays.fill(dp[1], Integer.MAX_VALUE);
// 遍历每个字母
for (int i = 2; i <= word.length(); i++) {
int v = ca[i - 1] - 'A';
// 遍历上一个阶段键位
for (int j = 0; j < 26; j++) {
if (dp[i % 2][j] == Integer.MAX_VALUE) {
continue;
}
int preV = ca[i - 2] - 'A';
dp[(i + 1) % 2][j] = Math.min(dp[(i + 1) % 2][j], dp[i % 2][j] + help(preV, v));
dp[(i + 1) % 2][preV] = Math.min(dp[(i + 1) % 2][preV], dp[i % 2][j] + help(j, v));
if (i == word.length()) {
ans = Math.min(ans, dp[(i + 1) % 2][j]);
ans = Math.min(ans, dp[(i + 1) % 2][preV]);
}
}
Arrays.fill(dp[i % 2], Integer.MAX_VALUE);
}
return ans;
}
// 计算距离
public int help(int a, int b) {
int x = a / 6, y = a % 6;
int x2 = b / 6, y2 = b % 6;
return (int)(Math.abs(x - x2)) + (int)(Math.abs(y - y2));
}
}
word 的长度。
如果该题解对你有帮助，点个赞再走呗~
