514 自由之路（动态规划）

超、凢脫俗 2022-08-30 01:43 109阅读 0赞

**1. 问题描述：**

电子游戏“辐射4”中，任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘，并使用表盘拼写特定关键词才能开门。给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。最初，ring 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。旋转 ring 拼出 key 字符 key\[i\] 的阶段中：  
您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key\[i\] 。  
如果字符 key\[i\] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。

**示例：**

输入: ring = "godding", key = "gd"  
输出: 4

**解释:**  
对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。  
对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。  
当然, 我们还需要1步进行拼写。  
因此最终的输出是 4。

**提示：**  
ring 和 key 的字符串长度取值范围均为 1 至 100；  
两个字符串中都只有小写字符，并且均可能存在重复字符；  
字符串 key 一定可以由字符串 ring 旋转拼出。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/freedom-trail

**2. 思路分析：**

对于这种需要**尝试所有可能方案**的字符串问题可以考虑**字符串dp**，而且数据范围比较小应该是可以解决的。对于字符串dp感觉还是比较有难度的，主要是状态表示和状态计算的过程比较难想，一般来说字符串dp有两种，第一种是一维的字符串dp，这个时候题目中只有一个字符串，第二种是二维的字符串dp，一般题目中涉及到两个字符串。对于动态规划的题目，y总在视频中总结dp的求解有以下两个常规步骤：① 状态表示 ② 状态计算。对于这道题目来说转盘可以转动等价于指针指向字符出的指针移动，所以我们考虑指向字符串的指针移动会比较好处理，下图是主要的分析过程，因为涉及到两个字符串，所以我们可以定义二维的dp，dp\[i\]\[j\]表示已经输出了key的前i个字符而且输出key\[i\]的时候指针位于ring\[j\]的所有方案的最小值（状态表示很难想，一般我们都是**考虑前i个字符**....），怎么样进行状态的转移呢？可以发现我们可以**考虑上一个状态**（也即上一步），因为求解的是最小值所以肯定会进行指针的移动所以我们可以考虑上一步，也即指针位于k的状态（指针k可以位于1,2,...n，n为ring的字符串长度，下标从1开始）所以我们可以枚举上一个所有可能的集合对应的状态进行状态计算，上一个状态指针k到当前的状态指针j的位置可能存在两种尝试的方案，第一种是顺时针转，第二种是逆时针转，顺时针转的步数为abs(k - j)，逆时针转的步数为n - abs(k - j)，两者取一个min，枚举上一步可能的状态到当前的状态的所有集合，取一个min就是当前dp\[i\]\[j\]状态的值。感觉主要的难点在于状态表示，我们可以考虑前i个字符....结合题目中给出的某些变量进行定义，状态计算的时候考虑上一个可能的状态到当前的状态怎么样进行计算。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

class Solution:
        def findRotateSteps(self, ring: str, key: str) -> int:
            n, m = len(ring), len(key)
            ring = " " + ring
            key = " " + key
            dp = [[10 ** 8] * (n + 1) for i in range(m + 1)]
            # 输出了前i个字符指针位于1的位置的时候操作步数为0
            dp[0][1] = 0
            # 下标从1开始比较
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    # 只有当第key的i个字符等于ring的第j个字符的时候才是有效的
                    if key[i] == ring[j]:
                        # 考虑倒数第二步指针位于第k步, 也即上一个状态
                        for k in range(1, n + 1):
                            t = abs(k - j)
                            dp[i][j] = min(dp[i][j], dp[i - 1][k] + min(t, n - t) + 1)
            # 因为输出了m个字符但是指针不知道位于哪个位置所以需要枚举一遍求解出最小值
            res = 10 ** 8
            for i in range(1, n + 1):
                res = min(res, dp[m][i])
            return res

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/6575e1726d974493919d0cfa48a7529d.png