1183 . 编辑距离 - c++编程基础

1183 . 编辑距离时间限制：1 秒空间限制：65536 KB 分值: 0 编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。例如将kitten一字转成sitting： sitten （k->s） sittin （e->i） sitting （->g）所以kitten和sitting的编辑距离是3。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。给出两个字符串a,b，求a和b的编辑距离。 Input

第1行：字符串a(a的长度 <= 1000)。
第2行：字符串b(b的长度 <= 1000)。

Output

输出a和b的编辑距离

Input 示例

kitten
sitting

Output 示例

动态规划，编辑距离，老问题了：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int main(){ string word1,word2; cin>>word1>>word2; vector
      
        f(word2.length()+1); int upper_left=0;//记录f[i-1][j-1]; for(size_t i=0;i<=word2.size();++i) f[i]=i; for(size_t i=1;i<=word1.size();++i){ upper_left=f[0]; f[0]=i; for(size_t j=1;j<=word2.size();++j){ int upper=f[j]; if(word1[i-1]==word2[j-1]) f[j]=upper_left; else f[j]=1+min(upper_left,min(f[j],f[j-1])); //f[j-1]表示dp[i][j-1],f [j]表示dp[i][j] upper_left=upper; } } cout<< f[word2.length()]<