leetcode 514. 自由之路

(https://leetcode-cn.com/problems/freedom-trail/)

刚看的时候觉得应该是个贪心吧，用idx表示12：00指向的ring字符上的位置，pos[i]里面存字符'a'+i在ring中出现的所有的位置，对于key上的每一个字符，我们都需要在ring上做出决定后，才能继续key的下一个字符，对于每一阶段我们找出一个离12：00方向最近的ring[j] == key[i]，这样的话每一步取最近的，最终也应该是最近的。

​ 我刚开始是这样认为的，但是写代码写到一半的时候发现不对了，对于key上的一个字符key[i]，我们需要在pos[key[i] - 'a']中找到离idx最近的那个位置，但是如果有两个位置与idx的距离相等怎么办？随便选一个？肯定不对，因为尽管不同位置对当前这个阶段的贡献是一样的，但对后面的状态肯定有不同的影响，因为idx变了。

​ 这里的卡顿让我想到了可能会有其他可能性，即在当前阶段即使我不选择离idx最近的那个位置，最终的答案有可能会更优。对于这种情况，我们就很自然的想到暴力dfs了，把下一阶段的所有状态都给算出来，在用当前状态的值与其所对应的下一阶段的值相加取最小。但是暴力dfs的复杂度很高，我们就想到能不能记忆化一下，一直dfs到最后的状态，将其所对应的状态值给记录下来返回上一个状态，然后不断往上。在想一想其实连栈都可以给省掉，这样就得出了最终的动态规划方法

class Solution {
public:
    vector<int> pos[26];
    int findRotateSteps(string ring, string key) {
        for (int i = 0; i < 26; i++) pos[i].clear();
        int n = ring.size(), m = key.size();
        for (int i = 0; i < n; i++){
            pos[ring[i]-'a'].push_back(i);
        }
        //dp[i][j]表示当遍历到第i个字符时，idx在ring上j位置的最小代价
        vector<vector<int>> dp(m+1, vector<int>(n+1, -1));
        for (int j = 0; j <= n; j++) dp[m][j] = 0;
        for (int i = m-1; i >= 0; i--){
            int now = key[i]-'a';
            for (int j = 0; j < n; j++){
                for (int k = 0; k < pos[now].size(); k++){
                    int first = (pos[now][k]-j+n) % n, second = (j-pos[now][k]+n) % n;
                    int ret = min(first, second) + dp[i+1][pos[now][k]];
                    if (dp[i][j] == -1) dp[i][j] = ret;
                    else dp[i][j] = min(dp[i][j], ret);
                }
            }
        }
        return dp[0][0] + m;
    }
};