1205_题解_字符串的修改-最长公共子序列_dp

需要改动的次数为，目标字符串长度 - 两字符串最大公共子序列的长度

#include<iostream>
#include<cstring> 
using namespace std;
const int N=1010;

int n,m;
char a[N],b[N];
int f[N][N];  //f[i][j]表示a中前i个字符和b的前j个字符的公共子序列长度的最大值 

int main()
{
	cin>>a+1>>b+1;
	n = strlen(a+1);
	m = strlen(b+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)  
		{
			f[i][j]=max(f[i-1][j],f[i][j-1]); 
	//最后一个字符不相同的时候f[i-1][j]和f[i][j-1]包含了最后一个字符不同在公共子序列中的情况 
			if(a[i]==b[j])	f[i][j]=max(f[i][j],f[i-1][j-1]+1);
				//最后一个字符相同再更新f[i][j]最值 
		}
	cout<<n - f[n][m]; //步数为原长-最大公共子序列的长度 
	return 0;
}