一眼DP，看数据规模标程应该是O(1003)。
阶段肯定就是吟唱完一个字符，状态和哪个字符在12:00点有关。
所以我们定义 dp[i][j] := 吟唱完keys[0~i]后，rings[j]停在12:00点所需要的最少步数。
转移方程：dp[i][j] = min(dp[i-1][k] + steps(k, j) + 1) if keys[i] == rings[j] else +inf.
第i-1字符吟唱完ring停留在k，第i个字符吟唱完ring停留在j (rings[j] 必须和 keys[i] 相同)，steps(k, j)表示ring从k转到j所需要的最少步数，最后还要+1，表示吟唱当前字符所需要的额外步骤。
边界条件：对于第0个字符，ring一开始停留在第0个字符，最小步数就是1 + steps(0, key[0])。
时间复杂度：O(mn2)
空间复杂度：O(mn) 可以降维到 O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: int findRotateSteps(string ring, string key) { const int n = ring.size(); const int m = key.size(); auto steps = [n](int i, int j) { return min(abs(i - j), n - abs(i - j)); }; // dp[i][j] min steps to spell key[0~i] and ring[j] is at 12:00. vector<vector<int>> dp(m, vector<int>(n, INT_MAX/2)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { if (ring[j] != key[i]) continue; for (int k = 0; k < n; ++k) dp[i][j] = min(dp[i][j], 1 + (i == 0 ? steps(0, j) : (dp[i - 1][k] + steps(j, k)))); } return *min_element(begin(dp.back()), end(dp.back())); } }; |