动态规划
ref{:target=”_blank”}
C++ 代码
class Solution {
public:
int findRotateSteps(string ring, string key) {
// f[i][j] 表示 完成key的第i位时候,ring的位置在j;
// 所有这些情况中的min step
int m = ring.size(), n = key.size();
const int INF = 1e8; // 求最小值,初始化
vector<vector<int>> f(n+1, vector<int>(m+1, INF));
// 前面添加一个 " ",方便初始化
ring = " " + ring;
key = " " + key;
f[0][1] = 0; // 初始状态
// 先枚举key的原因是,从ring肯定可以得到key的各个前缀,反之不一定有解
for(int i=1; i<=n; ++i) {
for(int j=1; j<=m; ++j) {
// 满足对应的条件
if(key[i] == ring[j]) {
for(int k=1; k<=m; ++k) {
int step = abs(k-j);
// 正反方向旋转
f[i][j] = min(f[i][j], f[i-1][k] + min(step, m-step)+1);
}
}
}
}
int res = INF;
// 需要枚举最后停留的位置
for(int i=1; i<=m; ++i) res = min(res, f[n][i]);
return res;
}
};