简答题 偏难
#22309

(编辑距离)给定两个字符串,每次操作可以选择删除(Delete)、插入(Insert)、替换(Replace),一个字符,求将第一个字符串转换为第二个字符串所需…

(编辑距离)给定两个字符串,每次操作可以选择删除(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; 
}


未登录也能判分,登录后才会记录
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。