# 【題解】Codeforces 1363F. Rotating Substrings

【範例】借還DP
【題目敘述】http://codeforces.com/contest/1363/problem/F

```#include <iostream>
#include <algorithm>
using namespace std;

int T, n, dp[2005][2005], suf_s[2005][26], suf_t[2005][26];
string s, t;

bool check(string x, string y){
sort(x.begin(), x.end());
sort(y.begin(), y.end());
return x == y;
}
int solve(int x, int y){
if (x < 0) return 0;
if (dp[x][y] != -1) return dp[x][y];
dp[x][y] = solve(x-1, y)+1;
if (s[x] == t[y]) dp[x][y] = min(dp[x][y], solve(x-1, y-1));
if (suf_s[x+1][t[y]-'a'] > suf_t[y+1][t[y]-'a']) dp[x][y] = min(dp[x][y], solve(x, y-1));
return dp[x][y];
}

int main() {
cin >> T;
while (T--){
cin >> n;
cin >> s >> t;
if (!check(s, t)){
cout << -1 << "\n";
continue;
}
for (int i = 0; i <= n; i++){
for (int j = 0; j <= n; j++){
dp[i][j] = -1;
}
for (int j = 0; j < 26; j++){
suf_s[i][j] = 0;
suf_t[i][j] = 0;
}
}
for (int i = n-1; i >= 0; i--){
for (int j = 0; j < 26; j++){
suf_s[i][j] = suf_s[i+1][j];
suf_t[i][j] = suf_t[i+1][j];
}
suf_s[i][s[i]-'a']++;
suf_t[i][t[i]-'a']++;
}
cout << solve(n-1, n-1) << "\n";
}
}
```