labuladong 的算法小抄 > 第二章、手把手刷动态规划 > 用动态规划玩游戏 > 动态规划帮我通关了《辐射4》

动态规划帮我通关了《辐射4》

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
514. Freedom Trail	514. 自由之路	🔴

———–

本文的封面图是一款叫做《辐射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);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int findRotateSteps(string ring, string key);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def findRotateSteps(ring: str, key: str) -> int:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func findRotateSteps(ring string, key string) int {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var findRotateSteps = function(ring, 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);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int dp(string ring, int i, string key, int j);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def dp(ring: str, i: int, key: str, j: int) -> int:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func dp(ring string, i int, key string, j int) int

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var dp = function(ring, i, key, 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, int j) {
    // base case，完成输入
    if (j == key.length()) return 0;
    // ...
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int dp(string ring, int i, string key, int j) {
    // base case，完成输入
    if (j == key.length()) return 0;
    // ...
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def dp(ring: str, i: int, key: str, j: int) -> int:
    # base case，完成输入
    if j == len(key):
        return 0
    # ...

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func dp(ring string, i int, key string, j int) int {
    // base case，完成输入
    if j == len(key) {
        return 0
    }
    // ...
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var dp = function(ring, i, key, j) {
    // base case，完成输入
    if (j === key.length) return 0;
    // ...
};

接下来，思考一下如何根据状态做选择，如何进行状态转移？

「选择」就是「如何拨动指针得到待输入的字符」。

再具体点就是，对于现在想输入的字符 key[j]，我们可以如何拨动圆盘，得到这个字符？

比如说输入 ring = "gdonidg"，现在圆盘的状态如下图：

假设我想输入的字符 key[j] = "d"，圆盘中有两个字母 "d"，而且我可以顺时针也可以逆时针拨动指针，所以总共有四种「选择」输入字符 "d"，我们需要选择操作次数最少的那个拨法。

大致的代码逻辑如下：

int dp(String ring, int i, String, int j) {
    // base case 完成输入
    if (j == key.length()) return 0;
    
    // 做选择
    int res = Integer.MAX_VALUE;
    for (int k : [字符 key[j] 在 ring 中的所有索引]) {
        res = min(
            把 i 顺时针转到 k 的代价,
            把 i 逆时针转到 k 的代价
        );
    }
    
    return res;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int dp(string ring, int i, string key, int j) {
    // base case 完成输入
    if (j == key.length()) return 0;
    
    // 做选择
    int res = INT_MAX;
    for (int k : {index of character key[j] in ring}) {
        res = min(
            cost of clockwise rotation from i to k,
            cost of counterclockwise rotation from i to k
        );
    }
    
    return res;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def dp(ring: str, i: int, key: str, j: int) -> int:
    # base case 完成输入
    if j == len(key): return 0
    
    # 做选择
    res = float("inf")
    for k in [index for index, char in enumerate(ring) if char == key[j]]:
        res = min(
            abs(k-i),
            len(ring)-abs(k-i)
        )
    
    return res

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func dp(ring string, i int, key string, j int) int {
    // base case 完成输入
    if j == len(key) {
        return 0
    }
    
    // 做选择
    res := math.MaxInt64
    for _, k := range [所有字符key[j]在ring中的索引] {
        res = min(
            转到k顺时针的代价,
            转到k逆时针的代价,
        )
    }
    
    return res
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var dp = function(ring, i, key, j) {
    // base case 完成输入
    if (j === key.length) return 0;
    
    // 做选择
    var res = Infinity;
    for (var k of [字符 key[j] 在 ring 中的所有索引]) {
        res = Math.min(
            把 i 顺时针转到 k 的代价,
            把 i 逆时针转到 k 的代价
        );
    }
    
    return res;
}

至于到底是顺时针还是逆时针，其实非常好判断，怎么近就怎么来；但是对于圆盘中的两个字符 "d"，还能是怎么近怎么来吗？

不能，因为这和 key[i] 之后需要输入的字符有关，还是上面的例子：

如果输入的是 key = "di"，那么即便右边的 "d" 离得近，也应该去左边的 "d"，因为左边的 "d" 旁边就是 "i"，「整体」的操作数最少。

那么，应该如何判断呢？其实就是穷举，递归调用 dp 函数，把两种选择的「整体」代价算出来，然后再做比较就行了。

讲到这就差不多了，直接看代码吧：

class Solution {
    // 字符 -> 索引列表
    HashMap<Character, List<Integer>> charToIndex = new HashMap<>();
    // 备忘录
    int[][] memo;

    /* 主函数 */
    public int findRotateSteps(String ring, String key) {
        int m = ring.length();
        int n = key.length();
        // 备忘录全部初始化为 0
        memo = new int[m][n];
        // 记录圆环上字符到索引的映射
        for (int i = 0; i < ring.length(); i++) {
            char c = ring.charAt(i);
            if (!charToIndex.containsKey(c)) {
                charToIndex.put(c, new LinkedList<>());
            }
            charToIndex.get(c).add(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.length()) return 0;
        // 查找备忘录，避免重叠子问题
        if (memo[i][j] != 0) return memo[i][j];
        
        int n = ring.length();
        // 做选择
        int res = Integer.MAX_VALUE;
        // ring 上可能有多个字符 key[j]
        for (int k : charToIndex.get(key.charAt(j))) {
            // 拨动指针的次数
            int delta = Math.abs(k - i);
            // 选择顺时针还是逆时针
            delta = Math.min(delta, n - delta);
            // 将指针拨到 ring[k]，继续输入 key[j+1..]
            int subProblem = dp(ring, k, key, j + 1);
            // 选择「整体」操作次数最少的
            // 加一是因为按动按钮也是一次操作
            res = Math.min(res, 1 + delta + subProblem);
        }
        // 将结果存入备忘录
        memo[i][j] = res;
        return res;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
public:
    // 字符 -> 索引列表
    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 = vector<vector<int>>(m, vector<int>(n, 0));
        // 记录圆环上字符到索引的映射
        for (int i = 0; i < ring.size(); i++) {
            char c = ring[i];
            charToIndex[c].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);
        }
        // 将结果存入备忘录
        memo[i][j] = res;
        return res;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List
from collections import defaultdict

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        # 字符 -> 索引列表
        charToIndex = defaultdict(list)
        # 备忘录
        memo = [[0] * len(key) for _ in range(len(ring))]
        # 记录圆环上字符到索引的映射
        for i, c in enumerate(ring):
            if c not in charToIndex:
                charToIndex[c] = []
            charToIndex[c].append(i)
        # 圆盘指针最初指向 12 点钟方向，
        # 从第一个字符开始输入 key
        return self.dp(ring, 0, key, 0, charToIndex, memo)

    # 计算圆盘指针在 ring[i]，输入 key[j..] 的最少操作数
    def dp(self, ring: str, i: int, key: str, j: int, charToIndex: defaultdict, memo: List[List[int]]) -> int:
        # base case 完成输入
        if j == len(key):
            return 0
        # 查找备忘录，避免重叠子问题
        if memo[i][j]:
            return memo[i][j]

        n = len(ring)
        # 做选择
        res = float('inf')
        # ring 上可能有多个字符 key[j]
        for k in charToIndex[key[j]]:
            # 拨动指针的次数
            delta = abs(k - i)
            # 选择顺时针还是逆时针
            delta = min(delta, n - delta)
            # 将指针拨到 ring[k]，继续输入 key[j+1..]
            subProblem = self.dp(ring, k, key, j + 1, charToIndex, memo)
            # 选择「整体」操作次数最少的
            # 加一是因为按动按钮也是一次操作
            res = min(res, 1 + delta + subProblem)

        # 将结果存入备忘录
        memo[i][j] = res
        return res

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func findRotateSteps(ring string, key string) int {
    // 字符 -> 索引列表
    charToIndex := make(map[byte][]int)
    // 记录圆环上字符到索引的映射
    for i := 0; i < len(ring); i++ {
        c := ring[i]
        charToIndex[c] = append(charToIndex[c], i)
    }
    // 备忘录全部初始化为 0
    // 注意内部 slice 的长度也要设置为 n
    memo := make([][]int, len(ring))
    for i := range memo {
        memo[i] = make([]int, len(key))
    }
    // 圆盘指针最初指向 12 点钟方向，从第一个字符开始输入 key
    return dp(ring, 0, key, 0, charToIndex, memo)
}

// 计算圆盘指针在 ring[i]，输入 key[j..] 的最少操作数
func dp(ring string, i int, key string, j int, charToIndex map[byte][]int, memo [][]int) int {
    // base case 完成输入
    if j == len(key) {
        return 0
    }
    // 查找备忘录，避免重叠子问题
    if memo[i][j] != 0 {
        return memo[i][j]
    }

    n := len(ring)
    // 做选择
    res := math.MaxInt32
    // ring 上可能有多个字符 key[j]
    for _, k := range charToIndex[key[j]] {
        // 拨动指针的次数
        delta := abs(k-i, n)
        // 将指针拨到 ring[k]，继续输入 key[j+1..]
        subProblem := dp(ring, k, key, j+1, charToIndex, memo)
        // 选择「整体」操作次数最少的
        // 加一是因为按动按钮也是一次操作
        res = min(res, 1+delta+subProblem)
    }
    // 将结果存入备忘录
    memo[i][j] = res
    return res
}

func abs(a, b int) int {
    if a > b {
        return b - a + n
    }
    return a - b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var findRotateSteps = function(ring, key) {
    // 字符 -> 索引列表
    const charToIndex = new Map();
    // 备忘录
    let memo = [];

    /* 主函数 */
    for (let i = 0; i < ring.length; i++) {
        const c = ring.charAt(i);
        if (!charToIndex.has(c)) {
            charToIndex.set(c, []);
        }
        charToIndex.get(c).push(i);
    }

    // 圆盘指针最初指向 12 点钟方向，
    // 从第一个字符开始输入 key
    return dp(ring, 0, key, 0);
        
    /* 计算圆盘指针在 ring[i]，输入 key[j..] 的最少操作数 */
    function dp(ring, i, key, j) {
        // base case 完成输入
        if (j == key.length) return 0;
        // 查找备忘录，避免重叠子问题
        if (memo[i][j]) return memo[i][j];

        const n = ring.length;
        // 做选择
        let res = Infinity;
        // ring 上可能有多个字符 key[j]
        for (let k of charToIndex.get(key.charAt(j))) {
            // 拨动指针的次数
            let delta = Math.abs(k - i);
            // 选择顺时针还是逆时针
            delta = Math.min(delta, n - delta);
            // 将指针拨到 ring[k]，继续输入 key[j+1..]
            let subProblem = dp(ring, k, key, j + 1);
            // 选择「整体」操作次数最少的
            // 加一是因为按动按钮也是一次操作
            res = Math.min(res, 1 + delta + subProblem);
        }
        // 将结果存入备忘录
        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 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释