动态规划帮我通关了《辐射4》 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：动态规划帮我通关了《辐射4》

评论礼仪 见这里，违者直接拉黑。

[xiaoye-2018]

这孩子打的游戏可真多，果然优秀的人各方面都很优秀

[mengfanxiao777]

动态规划的核心：状态和选择。状态：指针所在位置，key中字符位置；选择：逆时针或顺时针，当出现多个相同字符时选择最小的

[FOREST-QIN]

Java 版本 有需要可以参考一下

class Solution {
    Map<Character, ArrayList<Integer>> charMap;
    int[][] memo;
    
    public int findRotateSteps(String ring, String key) {
        int m = ring.length();
        int n = key.length();
        this.charMap = new HashMap<>();
        for (int i = 0; i < ring.length(); i++) {
            char ch = ring.charAt(i);
            charMap.putIfAbsent(ch, new ArrayList<>());
            charMap.get(ch).add(i);
        }
        this.memo = new int[m][n];
        for (int[] array : memo) Arrays.fill(array, -1);
        return dp(ring, 0, key, 0);
    }
    
    private int dp(String ring, int i, String key, int j) {
        if (j == key.length()) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        
        int n = ring.length();
        int res = Integer.MAX_VALUE;
        
        for (int k : charMap.get(key.charAt(j))) {
            int diff = Math.abs(k - i);
            diff = Math.min(diff, n - diff);
            int subProblem = dp(ring, k, key, j + 1);
            res = Math.min(res, 1 + diff + subProblem);
        }
        memo[i][j] = res;
        return res;
    }
}

[h1heart]

简洁的Python：

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        char_dict = collections.defaultdict(list)
        for index, c in enumerate(ring):
            char_dict[c].append(index)
        
        m = len(ring)
        n = len(key)

        # d[i][j]: 当指针指向ring[i]时，拼写key[j:]的最小步数
        # base case: d[i][n] = 0
        d = [[0] * (n + 1) for i in range(m)]

        for j in range(n - 1, -1, -1):
            for i in range(m):
                for k in char_dict[key[j]]:
                    step = min(abs(k - i), abs(m - abs(k - i)))
                    d_i_j = d[k][j + 1] + step + 1
                    d[i][j] = min(d[i][j], d_i_j) if d[i][j] else d_i_j
        
        return d[0][0]

[h1heart]

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        char_dict = collections.defaultdict(list)
        for index, c in enumerate(ring):
            char_dict[c].append(index)
        
        m = len(ring)
        n = len(key)

        # d[i][j]: 当指针指向ring[i]时，拼写key[j:]的最小步数
        # base case: d[i][n] = 0
        d = [[0] * (n + 1) for i in range(m)]

        for j in range(n - 1, -1, -1):
            for i in range(m):
                for k in char_dict[key[j]]:
                    step = min(abs(k - i), abs(m - abs(k - i)))
                    d_i_j = d[k][j + 1] + step + 1
                    d[i][j] = min(d[i][j], d_i_j) if d[i][j] else d_i_j
        
        return d[0][0]

[zzbb9944]

得到ring中所有字符的索引这样竟然是对的？我自己写的，现在觉得是错的，之后的重复字符算出来的value跟之前的不一样，put后会覆盖之前的值，那就错了呀~~~

        for(int i = 0; i < ring.length(); i++){
            char c = ring.charAt(i);
            List<Integer> indexs = new ArrayList<>();
            int a = ring.indexOf(c);
            while(a != -1){
                indexs.add(a);
                a = ring.indexOf(c, a+1);
            }
            map.put(c, indexs);
        }

[YiRu-hub]

srds，这不是Java写的吗hhh

[zhongweiLeex]

修改第二版代码

class Solution {
    public int findRotateSteps(String ring, String key) {
        //保存 ring中的所有字符对应的 索引 
        HashMap<Character,List<Integer>> map = new HashMap<>();
        
        for(int i = 0; i<ring.length();i++){

            if(!map.containsKey(ring.charAt(i))){
                map.put(ring.charAt(i),new LinkedList<>());
            }
            map.get(ring.charAt(i)).add(i);
        }
        //dp[i][j] 表示  当前ring指针 指向 ring[i] 需要凑出 key[j..] 需要的最少步骤
        int[][] dp = new int[ring.length()+1][key.length()+1];
        for(int j = key.length()-1 ; j >= 0 ; j--){
            for(int i = 0; i< ring.length(); i++){
                char target = key.charAt(j);
                List<Integer> list = map.get(target);
                int result  = Integer.MAX_VALUE;
                for(int index : list){//所有key[j] 对应的 ring相同字符的索引 index ， 计算 从index中
                    int step1 = Math.abs(index - i);//顺时针旋转
                    int step2 = ring.length()-step1;//逆时针旋转
                    int minStep = Math.min(step1,step2);
                    result = Math.min(result,minStep+1+dp[index][j+1]);//所有 ring中与 key中相同字符的 旋转次数最少的 
                }
                dp[i][j] = result;
            }
        }
        return dp[0][0];
    }
}

[Letter0]

请问为什么j指针要逆序遍历呢

[Chen-yongcheng]

因为在遍历第j个字符时，影响它最优步数的，是下一个或者下n个字符串，和前j-1个字符串无关，所以dp[i][j]中的j才能是key[j...]，所以得逆序，正序确定不了最优解，就相当于知道了结果往前推。

[Chen-yongcheng]

第二种方法：key第k个字符所需的最小步数与之所以和第j-1个无关，是因为不能确定转盘在第j-1个字符的指向，所以定义数组dp[i][j]为ring在第j-1个字符指向第i个字符时，key[....j]所需的最大步数。 https://leetcode.cn/problems/freedom-trail/solution/javadong-tai-gui-hua-by-viktorxhzj/

[Yjppj]

感觉自底向上的dptable解法的难度要小于dp函数，因为dp函数里面用到了递归，感觉递归的那一部分总是不好理解，比较有难度，不知道有没有人和我一样？

[Yjppj]

请问dptable解法dp数据的定义是什么？

[zhongweiLeex]

请问dptable解法dp数据的定义是什么？

• 这个需要看具体题目定义的 ， 每种题目的dp数组的定义不尽相同， 需要自己体会，其实 这里的使用 dp数组和dp递归方法的形式 就是 BFS 和 DFS 的区别 。
• 关于递归方法不好理解，建议看看东哥之前反复提及的 不要试图脑中压栈， 只要用一种情况带入递归方法就行，想要从后往前递归出来，是不太现实的，比较容易绕进去。

[labuladong]

@zhongweiLeex 整体上就是这个意思，不过有一个小错误：动态规划的递归方法和迭代方法是自顶向下和自底向上的关系，而不是 DFS 和 BFS 的关系，具体可以看下 动态规划详解。

[WFHJSZR-WAN]

class Solution {
    // 字符，索引列表
    HashMap<Character,ArrayList<Integer>>charToIndex;
    // 备忘录
    int [][]memo;
    public int findRotateSteps(String ring, String key) {
        int m=ring.length();
        int n=key.length();
        memo=new int[m][n];
        // 备忘录全部初始化为
        for(int []array:memo){
            Arrays.fill(array,0);
        }
        // 记录圆环上字符到索引的映射
        charToIndex=new HashMap();
        for(int i=0;i<m;i++){
            char ch = ring.charAt(i);
            // putIfAbsent() 方法会先判断指定的键（key）是否存在，不存在则将键/值对插入到 HashMap 中。
            charToIndex.putIfAbsent(ch, new ArrayList<>());
            charToIndex.get(ch).add(i);
        }
        // 圆盘指针最初指向 12 点钟方向，
        // 从第一个字符开始输入 key
        return dp(ring,0,key,0);

    }
     // 计算圆盘指针在 ring[i]，输入 key[j..] 的最少操作数
     int dp(String ring,int i,String key,int j){
        //  完成输入
        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;

     }
}

[zhongweiLeex]

@zhongweiLeex @labuladong result = Math.min(result,step+1+dp[index][j-1]); 感觉这个从前往后的dp数组的的定义行不通，因为初始指针的位置没法定。我们只能从前一个匹配字符的索引推断出后一个字符的初始指针位置，而不能反过来。

懂了，从base case 初始化那块就应该看出来，j 前面都没有初始化 根本是不确定的，对的 ， 谢谢你！

[Maschinist-LZY]

dp数组解法 C++

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int m = ring.size();
        int n = key.size();
        vector<int> pos_r[26];
        for(int i=0; i<m; i++){
            pos_r[ring[i] - 'a'].push_back(i);
        }
        vector<vector<int>> dp(m+1,vector<int>(n+1,1000));
        for(int i=0; i<m; i++){
            dp[i][n] = 0;
        }
        for(int j=n-1; j>=0; j--){
            for(int i=0; i<m; i++){
                int res = INT_MAX;
                for(int k : pos_r[key[j]-'a']){
                    int delta = abs(k-i);
                    delta = min(delta, m - delta);
                    res = min(res, dp[k][j+1] + delta + 1);
                }
                dp[i][j] = res;
            }
        }
        return dp[0][0];
    }
};

[potatogit]

这个递归解法的时间复杂度是ring.length的key.length次幂吗？？有点震惊

[LebronHarden1]

"当时我看了一眼就做出来了" (手动狗头doge)

[JerryWuZiJie]

感觉去掉memo就跟dfs差不多了

[labuladong]

动态规划本来就是暴力穷举，只是用备忘录消除重叠子问题罢了。

[yonggui-yan]

打卡。

[lpdswing]

py版

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

        @cache
        def dp(i, j):
            # 计算在ring[i], key[j..]的最少操作数
            if j == len(key):
                return 0
            n = len(ring)
            res = inf
            for k in char_idx[key[j]]:
                delta = abs(k - i)
                # 选择顺时针还是逆时针
                delta = min(delta, n - delta)
                # 把指针播到ring[k], 继续输入key[j+1..]
                sub = dp(k, j + 1)
                res = min(res, 1 + delta + sub)
            return res

        char_idx = defaultdict(list)
        for i, v in enumerate(ring):
            char_idx[v].append(i)
        return dp(0, 0)

[lauloong]

java版，压缩空间

class Solution {
    public int findRotateSteps(String ring, String key) {
        int rLen = ring.length(), kLen = key.length();
        HashMap<Character, List<Integer>> charToIndex = new HashMap<>();
        for(int i = 0; i < rLen; i++) {
            // 初始化charToIndex
            char c = ring.charAt(i);
            charToIndex.putIfAbsent(c, new LinkedList<>());
            charToIndex.get(c).add(i);
        }
        // i为ring上索引，j为key上索引
        // dp[i][j]为转盘指针指向i时，拼出[j...]后面字符的最小步骤数
        int[][] dp = new int[rLen + 1][2];

        // 每次更新step需要依赖j+1列上的所有结果
        // 空间压缩，但还需要一列来存贮j+1的结果，因为每次访问的位置不确定
        for(int j = kLen - 1; j >= 0; j--) {
            // 每轮更新dp[i][j]时的base case
            for(int i = rLen - 1; i >= 0; i--) {
                dp[i][1] = dp[i][0];
                dp[i][0] = Integer.MAX_VALUE;
            }
            for(int i = rLen - 1; i >= 0; i--) {
                for(Integer index : charToIndex.get(key.charAt(j))) {
                    int step = Math.min(Math.abs(index - i), rLen - Math.abs(index - i)) + 1 + dp[index][1];
                    dp[i][0] = Math.min(dp[i][0], step);
                }
            }
         }
        return dp[0][0];
    }
}

无论是否压缩空间，自下而上的运行速度比自顶向下慢一些是为什么呢？

[bruceeewong]

太强了，尤其是圆环位置转hashmap，Math.abs 算圆环两点距离，Math.min(delta, n - delta) 求顺逆时针最小值这几步技巧！

[CarlLy7]

同感，感觉能用HashMap来存储字符以及它所有的下标，这一步就很难想出来了

[ccbling26]

class Solution:
    # def find_best(self, i, j) -> int:
    #     if j >= self.n:
    #         return 0
    #     key = f"{i},{j}"
    #     if key in self.seen:
    #         return self.seen[key]
    #     if self.ring[i] == self.key[j]:
    #         res = 1 + self.find_best(i, j + 1)
    #     else:
    #         idx_list = self.ring_dict[self.key[j]]
    #         res = sys.maxsize
    #         for idx in idx_list:
    #             dis = min(abs(i - idx), self.m - abs(i - idx))
    #             res = min(res, dis + 1 + self.find_best(idx, j + 1))
    #     self.seen[key] = res
    #     return res

    # def findRotateSteps(self, ring: str, key: str) -> int:
    #     self.ring_dict = defaultdict(list)
    #     for i, c in enumerate(ring):
    #         self.ring_dict[c].append(i)
    #     self.ring = ring
    #     self.key = key
    #     self.m = len(ring)
    #     self.n = len(key)
    #     self.seen = {}
    #     return self.find_best(0, 0)
    
    def findRotateSteps(self, ring: str, key: str) -> int:
        ring_dict = defaultdict(list)
        for i, c in enumerate(ring):
            ring_dict[c].append(i)
        m = len(ring)
        n = len(key)
        dp = [[sys.maxsize] * m for _ in range(n)]
        idx_list = ring_dict[key[n - 1]]
        for idx in idx_list:
            dp[n - 1][idx] = 1
        for i in range(n - 2, -1, -1):
            idx_list_1 = ring_dict[key[i]]
            idx_list_2 = ring_dict[key[i + 1]]
            if key[i] == key[i + 1]:
                for j in idx_list_1:
                    dp[i][j] = dp[i + 1][j] + 1
                continue
            for j in idx_list_1:
                for k in idx_list_2:
                    dp[i][j] = min(dp[i][j], 1 + min(abs(j - k), m - abs(j - k)) + dp[i + 1][k])
        res = sys.maxsize
        for idx in ring_dict[key[0]]:
            res = min(res, dp[0][idx] + min(idx, m - idx))
        return res

[CarlLy7]

打卡，附上Java版本，注释的很清楚，感觉挺好理解的

public class FreedomTrail {

    //这个散列表用来记录ring中每个字符出现的索引位置
    HashMap<Character, ArrayList<Integer>> charIndex=new HashMap<>();
    //使用备忘录来消除重叠子问题
    int[][] memo;
    public int findRotateSteps(String ring, String key) {
        int m=ring.length();
        int n=key.length();
        memo=new int[m][n];
        for (int i = 0; i < m; i++) {
            char c = ring.charAt(i);
            //如果此时散列表中有这个字符的话，将这个索引位置添加到list中
            if(charIndex.containsKey(c)){
              charIndex.get(c).add(i);
            }else{
                //如果此时的散列表中没有这个字符的话，将这个字符以及它对应的索引加入到散列表中
                ArrayList<Integer> list=new ArrayList<>();
                list.add(i);
               charIndex.put(c,list);
            }
        }
        return dp(ring,0,key,0);
    }

    //声明一下dp函数的定义：从ring中的i位置开始，输入从key的j位置到最后位置所需要转动和按下去的最少次数
    private int dp(String ring, int i, String key, int j) {
        //base case:当j为key的最后一个的时候
        if(j==key.length()){
            return 0;
        }
        if(memo[i][j]!=0){
            return memo[i][j];
        }
        int n=ring.length();
        //开始做选择
        int res=Integer.MAX_VALUE;
        //得到key中我们此时需要输入的字符在ring中的所有的索引下标
        for (Integer k : charIndex.get(key.charAt(j))) {
            int distance=Math.abs(k-i);//求出此时的下标到ring中i位置的绝对距离
            //顺时针或者逆时针选择
            int choice=Math.min(distance,n-distance); //choice其实是这次的最小次数
            //接着递归下面的
            int subProblem=dp(ring,k,key,j+1);//subProblem其实是下面的问题的最小的次数
            res=Math.min(res,1+choice+subProblem);//加1是因为还要按下去
        }
        memo[i][j]=res;
        return res;
    }
}

[CarlLy7]

改正一下：上面的choice和subProblem应该是最小的转动次数，上面写的最小次数不严谨

[zhang9786]

是我看错了吗，最后的代码显示java写的，AI翻译的c++。但是最后东哥描述的是C++版本的，我学C++的，如果要是C++是写的话，记得把dp函数里面加上引用，否则会拷贝很多份ring字符串和key字符串，虽然说这个复制也能通过，但是和加上引用就是两个效率。有的题在递归里面不加引用很大几率超时。

[shiboys]

这个对于刚入动态规划坑的新手来说，想破天也很难联系到一起呀！
楼主还是想象力很丰富的，动手能力也是刚刚的

[Xiangjie-Yuan]

想问一下，这道题为什么不能将dp[i][j]定义为，当前指向ring的i位置，输入字符串为[0:i]时最少的操作数，这样base case为j<0时返回0？我测试过，这道题和之前魔塔那道题一样，只能倒着dp，不能正着dp，想问一下什么时候应该倒着，什么时候应该正着来，感觉不是很好分辨。同时，我发现有人说过，对于没有状态的题目，正着倒着dp都可以，这道题和魔塔那个只能倒着，我是不是能理解为，全部倒着dp，肯定没错，谢谢大家回复

[HCWGH]

备忘录递归、TreeSet查找key字符在ring中的左右（顺时针和逆时针）位置、取最小值

class Solution {
    Map<Character, TreeSet<Integer>> map = new HashMap<>();
    int[][] memo;

    //两种选择顺时针和逆时针
    public int findRotateSteps(String ring, String key) {
        for (int i = 0; i < ring.length(); i++) {
            char ch = ring.charAt(i);
            map.putIfAbsent(ch, new TreeSet<>());
            map.get(ch).add(i);
        }
        memo = new int[ring.length()][key.length()];
        for (int[] m : memo) {
            Arrays.fill(m, -1);
        }
        return dp(ring, key, 0, 0);
    }

    public int dp(String ring, String key, int i, int j) {
        if (j == key.length()) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        char keyC = key.charAt(j);
        char rC = ring.charAt(i);
        int min;
        //相等直接拼写操作数+1
        if (keyC == rC) {
            min = dp(ring, key, i, j + 1) + 1;
        } else {
            TreeSet<Integer> indexSet = map.get(keyC);
            Integer left = indexSet.floor(i);
            if (left == null) {
                left = indexSet.last();
            }
            Integer right = indexSet.ceiling(i);
            if (right == null) {
                right = indexSet.first();
            }
            int leftStep = left > i ? i + ring.length() - left : i - left;
            int rightStep = right < i ? ring.length() - i + right : right - i;
            //顺时针逆时针去最小值
            min = Math.min(dp(ring, key, left, j) + leftStep, dp(ring, key, right, j) + rightStep);
        }
        memo[i][j] = min;
        return min;
    }
}