题解 | #计算字符串的编辑距离#

解题思路：

• 知道用dp，那么dp[i][j]表示在动态规划过程中表示字符串s1走到i位置，以及字符串s2走到j位置，所需要的最短字符串距离（需要修改的最小次数）
• 一般情况下，dp[i][j]应该是通过三种操作（插入一个字符，删除一个字符，以及修改一个字符）得到的最小操作次数，先要判断一下$s1[i]==s2[j]s1[i]\; ==\; s2[j]$，如果相等则$dp[i][j]=dp[i-1][j-1]dp[i][j]\; =\; dp[i-1][j-1]$,否则有$dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1dp[i][j]\; =\; min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])\; +\; 1$。
• 再来处理边界情况，第一当$i==0andj==0i\; ==\backslash \; 0\backslash \; and\backslash \; j\backslash \; ==\backslash \; 0$时只需判断$dp[0][0]=s1[i]==s2[j]?0:1dp[0][0]\; =\; s1[i]\; ==\; s2[j]?\backslash \; 0\backslash \; :\backslash \; 1$,接下来判断$i==0i\; ==\; 0$时，判断$s{2}_{[0-j]}s2\_\{[0-j]\}$上是否存在s1[0],如果存在则最小距离为j,否则为j+1--即s2多出来部分的长度，同样的道理处理$j==0j\; ==\; 0$时s1的剩余部分长度。

#include<bits/stdc++.h>
using namespace std;
int solve(string &s1, string &s2, int i, int j, vector<vector<int>> &dp){
   if(dp[i][j] != -1) return dp[i][j];//如果已经计算直接返回
   int flag;
  //处理边界
   if(i == 0 && j == 0) dp[i][j] = s1[i] != s2[j];
   else if(i == 0){
       int flag = 0;
       for(int l = 0; l <= j; ++l){
           if (s1[i] == s2[l]) {
               flag = 1;
               break;
               }
       }
       if(flag) dp[i][j] = j;
       else dp[i][j] = j + 1;
   }
   else if(j == 0){
       int flag = 0;
       for(int l = 0; l <=i; ++l){
           if (s1[l] == s2[j]) {
               flag = 1;
               break;
               }
       }
       if (flag) dp[i][j] = i;
       else dp[i][j] = i+1;
   }
   else{//一般情况
       if(s1[i] == s2[j]) dp[i][j] = solve(s1, s2, i-1,j-1,dp);
       else dp[i][j] = min(solve(s1,s2,i-1,j-1,dp),min(solve(s1,s2,i-1,j,dp), solve(s1,s2,i,j-1,dp)))+1;
   }
   return dp[i][j];
}
int main(){
    string s1;
    string s2;
    cin>>s1;
    cin>>s2;
    vector<vector<int>> dp(s1.size(), vector<int>(s2.size(),-1));
    cout<<solve(s1, s2,s1.size()-1,s2.size()-1, dp)<<endl;
    return 0;
}