（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。#include <iostream> #include <string> #include <vector> using namespace std; int min(int x,int y,int z){ return min(min(x,y),z); } int edit_dist_dp(string str1,string str2){ int m=str1.length(); int n=str2.length(); vector<vector<int>> dp(m+1,vector<int>(n+1)); for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ if(i==0) dp[i][j]= ① ; else if(j==0) dp[i][j]= ② ; else if( ③ ) dp[i][j]= ④ ; else dp[i][j]=1+min(dp[i][j-1],dp[i-1][j], ⑤ ); } } return dp[m][n]; } int main(){ string str1,str2; cin>>str1>>str2; cout<<"Mininum number of operation:" <<edit_dist_dp(str1,str2)<<endl; return 0; }

组合题

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int min(int x,int y,int z){
return min(min(x,y),z);
}

int edit_dist_dp(string str1,string str2){
int m=str1.length();
int n=str2.length();
vector<vector<int>> dp(m+1,vector<int>(n+1));

for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(i==0)
dp[i][j]=     ①     ;
else if(j==0)
dp[i][j]=     ②     ;
else if(     ③     )
dp[i][j]=     ④     ;
 else
 dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],     ⑤     ); 
 }
 }
return dp[m][n];
}

int main(){
 string str1,str2;
 cin>>str1>>str2;
 cout<<"Mininum number of operation:"
 <<edit_dist_dp(str1,str2)<<endl;
 return 0; 
}

第1题单选

①处应填（）