leetcode：Freedom Trail 解题思路

输入：一个字符串ring首尾相连，表示一个圆盘的戒指，每个位置上都有一个字母与之对应，另一个字符串表示需要组合成的序列key。
要求：通过旋转ring来逐个匹配key中的字符，如果当前匹配成功，按下按钮，进行下一个字符的匹配，其中ring每旋转过一个字符，记录步数+1， 按下按钮步数+1。
输出：完全匹配key后，整个过程最少的步数
初一见整个题目莫名想起了电影《飞鹰计划》呢。。。
言归正传，第一感觉就是暴力dfs，求最小，但是感觉会超时，果不其然，提交了下面的代码之后，跑到第50个用例就不行了。。。

int findRotateSteps(string ring, string key){
    int r_len = ring.length(), k_len = key.length(), i, j;
    if(r_len == 0|| k_len == 0) return 0;
    vector<vector<int>> dist(r_len, vector<int>(r_len, 0));
    for(i = 0; i < r_len; i++)
        for(j = i; j < r_len; j++)
            dist[i][j]=dist[j][i]=min(j-i, i-j+r_len)+1;
    return helper(ring, key, r_len, k_len, 0, 0, 0, dist);
}
int helper(string ring, string key, int r_len, int k_len, int r_idx, int k_idx, int cur_steps, vector<vector<int>>& dist){
    if(k_idx == k_len)
        return cur_steps;
    int res = INT_MAX;
    for(int i = 0; i < r_len; i++){
        if(ring[i]==key[k_idx])
            res = min(res, helper(ring, key, r_len, k_len, i, k_idx+1, cur_steps+dist[r_idx][i], dist));
    }
    return res;
}

脑壳疼。。。
想了半天，想到用dp，创建二维数组dist，其中每个元素的初始值设置为INT_MAX
其中dist[i][j]表示：使用ring[j]来匹配到key[i]时所用的最短步骤,递推如下：
dist[i][j] = min(dist[i][j], dist[i-1][k]+min(abs(k-j), ring.length()-abs(k-j))+1)条件是{dist[i-1][k]!=INT_MAX,0<=k AC代码如下：

int findRotateSteps(string ring, string key){
    int r_len = ring.length(), k_len = key.length(), i, j, k;
    if(r_len == 0|| k_len == 0) return 0;
    vector<vector<int>> dist(k_len, vector<int>(r_len, INT_MAX));
    for( i = 0; i < r_len; i++)
        if(ring[i]==key[0])dist[0][i]=min(i, r_len-i)+1;
    for(i = 1; i < k_len; i++){
        vector<int> temp(dist[i-1]);
        for(j = 0; j < r_len; j++){
            if(temp[j]!=INT_MAX){
                for(k = 0; k < r_len; k++){
                    if(ring[k]==key[i]){
                        dist[i][k]=min(dist[i][k], temp[j]+min(abs(j-k), r_len-abs(j-k))+1);
                    }
                }
            }
        }
    }
    int res = INT_MAX;
    for(i = 0; i < r_len;i++)
        res = min(res, dist[k_len-1][i]);
    return res;
}