字符串dp+匹配

https://codeforces.com/problemset/problem/2050/E

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
using ll = long long;
using pii = pair<char, int>;
const double PI = acos(-1);
const int N =1e3+10;
const int mod = 1e9 + 7;
int dp[N][N];
void solve(){
	string a,b,c;
	cin>>a>>b>>c;
	int lena=a.size();
	int lenb=b.size();
	for(int i=1;i<=lena;i++){
		dp[i][0]=dp[i-1][0]+(a[i-1]!=c[i-1]);
//		cout<<dp[i][0]<<" ";
	}
	for(int i=1;i<=lenb;i++){
		dp[0][i]=dp[0][i-1]+(b[i-1]!=c[i-1]);
//		cout<<dp[0][i]<<" ";
	}
	for(int i=1;i<=lena;i++)
		for(int j=1;j<=lenb;j++){
			dp[i][j]=min(dp[i][j-1],dp[i-1][j])+1;
			if(a[i-1]==c[i-1+j]){ //现在有i个a的字符，j个b的字符
				dp[i][j]=min(dp[i-1][j],dp[i][j]);
			}
			if(b[j-1]==c[j-1+i]){
				dp[i][j]=min(dp[i][j],dp[i][j-1]);
			}
		}
	cout<<dp[lena][lenb]<<endl;
}
int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int T = 1;
	cin>>T;
	while (T--) {
		solve();
	}
	
	return 0;
}