本文的封面图是一款叫做《辐射4》的游戏中的一个任务剧情画面：

这个可以转动的圆盘类似是一个密码机关，中间偏上的位置有个红色的指针看到没，你只要转动圆盘可以让指针指向不同的字母，然后再按下中间的按钮就可以输入指针指向的字母。

只要转动圆环，让指针依次指向 R、A、I、L、R、O、A、D 并依次按下按钮，就可以触发机关，打开旁边的门。

至于密码为什么是这几个字母，在游戏中的剧情有暗示，这里就不多说了。

那么这个游戏场景和动态规划有什么关系呢？

我们来没事儿找事儿地想一想，拨动圆盘输入这些字母还挺麻烦的，按照什么顺序才能使得拨动圆盘所需的操作次数最少呢？

拨动圆盘的不同方法所需的操作次数肯定是不同的。

比如说你想把一个字母对准到指针上，你可以顺时针转圆盘，也可以逆时针转圆盘；而且某些字母可能不止出现一次，比如上图中大写字母 O 就在圆盘的不同位置出现了三次，你到时候应该拨哪个 O 才能使得整体的操作次数最少呢？

我们之前也多次说过，遇到求最值的问题，基本都是由动态规划算法来解决，因为动态规划本身就是运筹优化算法的一种嘛。

力扣上就有一道这个转盘游戏的算法题，难度还是 Hard，但我当时看了一眼就做出来了，因为我以前思考过生活中一个非常有意思的例子可以类比到这个问题，下面来简单介绍一下。

今天要讲的力扣第 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)，否则会报错。

至此，这道题就解决了，是不是和钢琴的例子有异曲同工之妙呢？