题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int minOperations(string s1, string s2, int x) {
int n=s1.size();
vector<int> a;
for(int i=0;i<n;i++) if(s1[i]!=s2[i]) a.push_back(i);
vector<vector<int>> f(n,vector<int>(n,-1));
if(a.size()==0) return 0;
if(a.size()%2==1) return -1;
std::function<int(int,int)> dfs=[&](int l,int r){
if(l>=r) return f[l][r]=0;
if(f[l][r]!=-1) return f[l][r];
f[l][r]=dfs(l+1,r-1)+min(x,abs(a[l]-a[r]));
if(l+2<=r) f[l][r]=min(f[l][r],dfs(l+2,r)+min(x,abs(a[l]-a[l+1])));
if(r-2>=l) f[l][r]=min(f[l][r],dfs(l,r-2)+min(x,abs(a[r]-a[r-1])));
return f[l][r];
};
int m=a.size();
return dfs(0,m-1);
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla