练琴时悟出的动态规划算法，帮我通关了《辐射4》
后台回复进群一起刷力扣😏
点击卡片可搜索关键词👇
读完本文，可以去力扣解决如下题目：
514. 自由之路（Hard）
本文的封面图是一款叫做《辐射4》的游戏中的一个任务剧情画面：
这个可以转动的圆盘类似是一个密码机关，中间偏上的位置有个红色的指针看到没，你只要转动圆盘可以让指针指向不同的字母，然后再按下中间的按钮就可以输入指针指向的字母。
只要转动圆环，让指针依次指向 R、A、I、L、R、O、A、D 并依次按下按钮，就可以触发机关，打开旁边的门。
至于密码为什么是这几个字母，在游戏中的剧情有暗示，这里就不多说了。
那么这个游戏场景和动态规划有什么关系呢？
我们来没事儿找事儿地想一想，拨动圆盘输入这些字母还挺麻烦的，按照什么顺序才能使得拨动圆盘所需的操作次数最少呢？
拨动圆盘的不同方法所需的操作次数肯定是不同的。
比如说你想把一个字母对准到指针上，你可以顺时针转圆盘，也可以逆时针转圆盘；而且某些字母可能不止出现一次，比如上图中大写字母 O 就在圆盘的不同位置出现了三次，你到时候应该拨哪个 O 才能使得整体的操作次数最少呢？
我们之前也多次说过，遇到求最值的问题，基本都是由动态规划算法来解决，因为动态规划本身就是运筹优化算法的一种嘛。
力扣上就有一道这个转盘游戏的算法题，难度还是 Hard，但我当时看了一眼就做出来了，因为我以前思考过生活中一个非常有意思的例子可以类比到这个问题，下面来简单介绍一下。
关注了我的视频号的朋友，知道我弹过李斯特和肖邦的几首钢琴曲，但是没练过钢琴的读者可能不知道，练习钢琴曲谱是需要提前确定「指法」的。
五线谱的音符七上八下的，两个手的手指必须互相配合，也就是说你必须确定好每个音符用哪只手的哪个手指来弹奏，写到谱子上。
比如说我很喜欢的一首曲子叫做《爱之梦》：
这是我当时练习使用的谱子，可以看到上面标记了很多指法：
音符上的数字 1 代表用大拇指，2 代表用食指，以此类推。按照确定下来的指法不断练习，形成肌肉记忆，就算是练会一首曲子了。
指法这东西因人而异，比如手大的人可以让中指跨到大拇指的左边，手小的人可能就有些别扭，那同一段谱子对应的指法可能就不一样。
那么问题来了，我应该如何设计指法，才能最小化手指切换的「别扭程度」，也就是最大化演奏的流畅度呢？
这里我就借助了动态规划算法技巧：手指的切换不就是状态的转移么？参考前文 动态规划套路详解，只要明确「状态」和「选择」就可以解决这个问题。
状态是什么？状态就是「当前需要弹奏的音符」和「当前的手的状态」。
当前需要弹奏的音符，无非就是钢琴上 88 个琴键中的一个；手的状态也很简单，五个手指头，每个手指头要么按下去了要么没按下去，2 的 5 次方 32 种情况，5 个二进制位就可以表示。
选择是什么？选择就是「这个音符应该由哪个手指头来弹」，无非就是穷举五个手指头。
当然，结合当前手的状态，做出每个选择需要对应代价的，刚才说过这个代价是因人而异的，所以我需要给自己定制一个损失函数，计算不同指法切换的「别扭程度」。
现在的问题就变成了一个标准的动态规划问题，根据损失函数做出「别扭程度」最小的选择，使得整段演奏最流畅……
当然，最后这个算法时间复杂度太高了，我们刚才分析的只是单个的音符，但如果串成曲子，时空复杂度还得再乘曲子的音符数，很大。
而且，这个损失函数很难量化，钢琴的黑白键命中难度不同，而且「别扭程度」只能靠感觉，有点不严谨……
不过，本就没必要计算整首曲子的指法，只需要计算某些复杂段落的指法即可，这个算法还是比较有效的。
扯了这么多题外话终于要步入正题了，今天要讲的力扣第 514 题「自由之路」和钢琴指法问题有异曲同工之妙，如果你能理解钢琴的例子，相信你也能很快做出这道算法题。
题目给你输入一个字符串ring代表圆盘上的字符（指针位置在 12 点钟方向，初始指向ring[0]），再输入一个字符串key代表你需要拨动圆盘输入的字符串，你的算法需要返回输入这个key至少进行多少次操作（拨动一格圆盘和按下圆盘中间的按钮都算是一次操作）。
函数签名如下：
int findRotateSteps(string ring, string key);
比如题目举的例子，输入ring = "godding", key = "gd"，对应的圆盘如下（大写只是为了清晰，实际上输入的字符串都是小写字母）：
我们需要输入key = "gd"，算法返回 4。
因为现在指针指的字母就是字母"g"，所以可以直接按下中间的按钮，然后再将圆盘逆时针拨动两格，让指针指向字母"d"，然后再按一次中间的按钮。
上述过程，按了两次按钮，拨了两格转盘，总共操作了 4 次，是最少的操作次数，所以算法应该返回 4。
我们这里可以首先给题目做一个等价，转动圆盘是不是就等于拨动指针？
原题可以转化为：圆盘固定，我们可以拨动指针；现在需要我们拨动指针并按下按钮，以最少的操作次数输入key对应的字符串。
那么，这个问题如何使用动态规划的技巧解决呢？或者说，这道题的「状态」和「选择」是什么呢？
「状态」就是「当前需要输入的字符」和「当前圆盘指针的位置」。
再具体点，「状态」就是i和j两个变量。我们可以用i表示当前圆盘上指针指向的字符（也就是ring[i]）；用j表示需要输入的字符（也就是key[j]）。
这样我们可以写这样一个dp函数：
int dp(string& ring, int i, string& key, int j);
这个dp函数的定义如下：
当圆盘指针指向ring[i]时，输入字符串key[j..]至少需要dp(ring, i, key, j)次操作。
根据这个定义，题目其实就是想计算dp(ring, 0, key, 0)的值，而且我们可以把dp函数的 base case 写出来：
int dp(string& ring, int i, string& key, int j) {
// base case，完成输入
if (j == key.size()) return 0;
// ...
}
接下来，思考一下如何根据状态做选择，如何进行状态转移？
「选择」就是「如何拨动指针得到待输入的字符」。
再具体点就是，对于现在想输入的字符key[j]，我们可以如何拨动圆盘，得到这个字符？
比如说输入ring = "gdonidg"，现在圆盘的状态如下图：
假设我想输入的字符key[j] = "d"，圆盘中有两个字母"d"，而且我可以顺时针也可以逆时针拨动指针，所以总共有四种「选择」输入字符"d"，我们需要选择操作次数最少的那个拨法。
大致的代码逻辑如下：
int dp(string& ring, int i, string& key, int j) {
// base case 完成输入
if (j == key.size()) return 0;
// 做选择
int res = INT_MAX;
for (int k : [字符 key[j] 在 ring 中的所有索引]) {
res = min(
把 i 顺时针转到 k 的代价,
把 i 逆时针转到 k 的代价
);
}
return res;
}
至于到底是顺时针还是逆时针，其实非常好判断，怎么近就怎么来；但是对于圆盘中的两个字符"d"，还能是怎么近怎么来吗？
不能，因为这和key[i]之后需要输入的字符有关，还是上面的例子：
如果输入的是key = "di"，那么即便右边的"d"离得近，也应该去左边的"d"，因为左边的"d"旁边就是"i"，「整体」的操作数最少。
那么，应该如何判断呢？其实就是穷举，递归调用dp函数，把两种选择的「整体」代价算出来，然后再做比较就行了。
讲到这就差不多了，直接看代码吧：
// 字符 -> 索引列表
unordered_map<char, vector<int>> charToIndex;
// 备忘录
vector<vector<int>> memo;
/* 主函数 */
int findRotateSteps(string ring, string key) {
int m = ring.size();
int n = key.size();
// 备忘录全部初始化为 0
memo.resize(m, vector<int>(n, 0));
// 记录圆环上字符到索引的映射
for (int i = 0; i < ring.size(); i++) {
charToIndex[ring[i]].push_back(i);
}
// 圆盘指针最初指向 12 点钟方向，
// 从第一个字符开始输入 key
return dp(ring, 0, key, 0);
}
// 计算圆盘指针在 ring[i]，输入 key[j..] 的最少操作数
int dp(string& ring, int i, string& key, int j) {
// base case 完成输入
if (j == key.size()) return 0;
// 查找备忘录，避免重叠子问题
if (memo[i][j] != 0) return memo[i][j];
int n = ring.size();
// 做选择
int res = INT_MAX;
// ring 上可能有多个字符 key[j]
for (int k : charToIndex[key[j]]) {
// 拨动指针的次数
int delta = abs(k - i);
// 选择顺时针还是逆时针
delta = min(delta, n - delta);
// 将指针拨到 ring[k]，继续输入 key[j+1..]
int subProblem = dp(ring, k, key, j + 1);
// 选择「整体」操作次数最少的
res = min(res, 1 + delta + subProblem);
// PS：加一是因为按动按钮也是一次操作
}
// 将结果存入备忘录
memo[i][j] = res;
return res;
}
这段代码是 C++ 写的，因为我觉得涉及字符串的算法 C++ 更方便一些，这里说一些语言相关的细节问题：
1、unordered_map就是哈希表，当访问不存在的键时，会自动创建对应的值，所以可以直接push_back而不用担心空指针错误。
2、min函数的参数都是 int 型，所以必须先用一个 int 型变量n存储ring.size()，然后调用min(delta, n - delta)，否则会报错。
至此，这道题就解决了，是不是和钢琴的例子有异曲同工之妙呢？
如果本文对你有帮助，可以点个「在看」或者「赞」，这样微信会给你推荐更多相似内容。
＿＿＿＿＿＿＿＿＿＿＿＿＿
学好算法靠套路，认准 labuladong，知乎、B站账号同名。公众号后台回复「进群」可加我好友，拉你进算法刷题群。
扫码关注我的微信视频号，不定期发视频、搞直播：