lanqiao OJ 239 最优包含

//编译代码不做过多解释，有疑问复习以下上面编译距离的题
#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
const int N = 1010 , INF = 1e9 ;
char a[N] ,b[N] ;
int f[N][N] ;//表示前i个字母由前j个字母转化的最少操作数
int main(){
  scanf("%s" , a + 1 ) ;
  scanf("%s" , b + 1 ) ;
  int n = strlen(a + 1) ;
  int m = strlen(b + 1) ;
  for(int i = 0 ; i <= n ; i++){
    for(int j = 0 ; j <= m ; j ++){
      f[i][j] = 1000000 ;
    }
  }
  for(int i = 0 ; i <= n ; i ++ )f[i][0]  =  i ;
  for(int j = 0 ; j <= m ; j  ++) f[0][j] = j ;
  for(int i = 1 ; i <= n ; i ++ ){
    for(int j = 1 ; j <= m ; j ++ ){
      f[i][j] = f[i-1][j] + 1  ;//只能进行删除操作
      if(a[i] == b[j]) f[i][j] = min(f[i][j] , f[i-1][j-1] ) ;
      else f[i][j] = min(f[i][j] , f[i-1][j-1] + 1) ;
      
    }
  }
  cout << f[n][m] - n + m << endl ;
  return 0 ;
}