最优包含

AC2553
类似编辑距离DP的题目

#include <iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;
char a[1005],b[1005];
int f[1005][1005];//f(i,j) a的前 i 个包含 b的前  j 个 的最小操作数 
int main(){
	memset(f,0x3f,sizeof f);
	scanf("%s",a+1);
	scanf("%s",b+1);
	int lena=strlen(a+1);
	int lenb=strlen(b+1);
	f[0][0]=0; 
	for(int i=1;i<=lena;i++){
		f[i][0]=0;
		for(int j=1;j<=lenb;j++){
			f[i][j]=f[i-1][j];
			//前 i-1个就可以包含b的前 j 个
			//所以前 i个 可以直接等于i-1的操作数（j相同条件） 
			if(a[i]==b[j]){
				f[i][j]=f[i-1][j-1];
				//根据我们的表达式
				// a的前 i 个包含 b的前  j 个 的最小操作数 
				//假如 a=abcd,b=adc
				//f(2,2)很明显是 2
				//f(3,3)由于a[3]=b[3]所以根本没影响等于f(2,2)=2 
			}
			f[i][j]=min(f[i][j],f[i-1][j-1]+1);
			//进行一次操作可以理解成让有一个没满足条件的字符串满足条件
			// //假如 a=abcd,b=adc
			//f(1,1)很明显是 1 
			//f(2,2)时,a[2]!=b[2]，就直接进行一次操作,操作具体干什么不重要
			//关键是结果为操作数加一,同时满足匹配  f(2,2)=f(1,1)+1;
		}
	} 
	cout<<f[lena][lenb];
  return 0;
}




//  freopen("testdata.in", "r", stdin);