【Leetcode 514】自由之路 —— 动态规划-Toy模板网

这篇具有很好参考价值的文章主要介绍了【Leetcode 514】自由之路 —— 动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

514. 自由之路

电子游戏“辐射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的下一个字符（下一阶段）, 直至完成所有拼写。

示例 1：

【Leetcode 514】自由之路 —— 动态规划,Leetcode,leetcode,动态规划,java

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

示例 2:

输入: ring = “godding”, key = “godding”
输出: 13

题目分析

经典动态规划问题，更多案例可见 Leetcode 动态规划详解

【Leetcode 514】自由之路 —— 动态规划,Leetcode,leetcode,动态规划,java

我们可以使用动态规划解决本题，解题思路：

状态定义：
- dp[i][j] 表示 key 的第 i 个字符， ring 的第 j 个字符与 12:00 方向对齐的最少步数
- pos[i] 表示字符 i 在 ring 中出现的位置集合，用来加速计算转移的过程
状态转移方程：枚举上一次与12:00方向对齐的位置k，此次需要从位置k旋转到位置j

$\displaystyle\min_k∈pos[key[i−1]] {dp[i−1][k] + min{abs(j − k), n − abs(j − k)} + 1}$

> min{abs(j − k), n − abs(j − k)} + 1从位置k旋转到位置j的最少步数

初始状态dp[0][i] = min{i, n - i} + 1，最终答案为 $\displaystyle\min_i=0^n-1 {dp[m-1][i]}$

动态规划一般用于求解具有重叠子问题和最优子结构的问题，例如最长公共子序列、背包问题、最短路径等。重叠子问题指的是在求解问题的过程中，多次用到相同的子问题，最优子结构指的是问题的最优解可以通过子问题的最优解来构造文章来源地址https://www.toymoban.com/news/detail-825720.html

class Solution {
    public int findRotateSteps(String ring, String key) {
        int n = ring.length(), m = key.length();
        // 字符 i 在 ring 中出现的位置集合，用来加速计算转移的过程
        List<Integer>[] pos = new List[26];
        for (int i = 0; i < 26; i++) {
            pos[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n; i++) {
            pos[ring.charAt(i) - 'a'].add(i);
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        for (int i : pos[key.charAt(0) - 'a']) {
            dp[0][i] = Math.min(i, n - i) + 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j : pos[key.charAt(i) - 'a']) {
                for (int k : pos[key.charAt(i - 1) - 'a']) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1);
                }
            }
        }
        return Arrays.stream(dp[m - 1]).min().getAsInt();
    }
}