20.11.11 leetcode514

题目链接：https://leetcode-cn.com/problems/freedom-trail/

题意：给你一个密码字符串key，现在给你一个环形密码锁，环形密码锁按顺时针排列是字符串ring，现在需要求在环形密码锁上最少操作多少次可以解开密码，环形密码锁可顺时针或逆时针旋转，只有移动到12点方向时才可以确认，移动一位算操作一次，确认也算操作一次。

分析：可以看出，我们前面的每次操作都会对后面有影响，这种类型的问题一般都是DP或者搜索，我们可以往dp的角度思考思考。因为涉及到的字符串只有两个，所以可以考虑dp数组的两维分别是两个字符串的某一位，具体点来说，可以设dp[i][j]为字符串key在第i位，而此时环形密码锁第j位在12点方向且已确认时的最少操作次数。这里要注意的是，有意义的dp[i][j]必须是key的第i位同ring的第j位是相同的。为了方便之后dp，可以设pos向量，存储字符都出现在ring的哪些位置，最后的dp部分内层有两个选择，一个是选择和当前key字符串所处字符相同的ring字符串的位置（可能有多个），一个是选择好当前ring字符串后，再选择key字符串前一个字符对应的ring字符串字符位置，有点绕，直接看代码把。

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int len1=ring.length(),len2=key.length();
        vector<int> pos[26];
        for(int i=0;i<len1;i++){
            pos[ring[i]-'a'].push_back(i);
        }
        vector< vector<int> > dp(len2,vector<int>(len1,0x3f3f3f3f));
        for(auto& v : pos[key[0]-'a']){
            dp[0][v]=min(v,len1-v)+1;
        }
        for(int i=1;i<len2;i++){
            for(auto& u :pos[key[i]-'a']){
                for(auto& v : pos[key[i-1]-'a']){
                    dp[i][u]=min(dp[i][u],dp[i-1][v]+min(abs(u-v),len1-abs(u-v))+1);
                }
            }
        }
        int mn=0x3f3f3f3f;
        for(auto& v:pos[key[len2-1]-'a']){
            mn=min(mn,dp[len2-1][v]);
        }
        return mn;
    }
};