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

#include <algorithm>
#include <iostream>
using namespace std;
/*动态规划经典问题之 编辑距离
1)dp[i][j]表示word1[i-1]结尾的单词和word2[j-1]结尾的单词2之间编辑成一致所需要的最小距离（最少操作次数）（之所以是表示i-1 j-1结尾，是因为会比较容易初始化）
2）递推公式。分多种情况讨论。
   1> word1[i-1]=word2[j-1]，此时两个单词的最小距离无需考虑当前位，等于word1[i-2]结尾的单词和Word2[j-2]结尾的单词的最小距离。即：dp[i][j]=dp[i-1][j-1]
   当word1[i-1]!=word2[j-1]时，此时需要通过删除一位、增加一位、替换一位的方式去让word1和Word2相同。在这里，由于我们考虑的是【最少操作次数】，所以此时建立在word1[i-2]和word2[j-2]已经通过最少操作次数达成一致后，再处理接下来不一致的这一位。且，删除一位和新增一位实际上是互逆的操作，我在word1删除1位=Word2新增一位，操作数都是1次，所以这可以作为同一种情况来讨论
   2> word1[i-1]!=word2[j-1]。可以删除（新增）Word1的最后一位（1次操作），往前推余下的最少次数就是要使Word1[i-2]的单词和Word2[j-1]的单词一致的最短距离dp[i-1][j]  即dp[i][j]=1+dp[i-1][j];
   3>同理，我们可以操作word2，删除（新增）末位，递推公式为：dp[i][j]=1+dp[i][j-1]
   4>替换操作，Word1和Word2的最后一位替换一次，此前的部分通过最短操作距离使Word1[i-2]和word2[j-2]达成一致。即dp[i][j]=1+dp[i-1][j-1];
最后综上，2>3>4>都是遍历的当前位不一致时的三种处理方式，我们要选择其中最短的距离，即dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1 
要注意min中比较三个数字时要用｛｝括起来
3）初始化。从递推公式可以看出，推导的顺序是从(i-1,j-1)->(i,j)  (i-1,j)->(i,j)  (i,j-1)->(i,j)  相当于是在i*j的二维方格里，从左往右从上往下，从左上往右下递推。所以初始化我们初始化方格的第一列和第一行即可，即dp[i][0] dp[0][j]  而dp[i][0]又代表word1[i-1]结尾的单词和Word2[-1]结尾的单词比较，Word2[0]结尾的单词仅有一位字母，所以-1就相当于是一个空串。所以word1[i-1]通过删除字母到达空串，要操作的即为i次（注意Word1里是0～i-1,实际操作次数就是1～i） 所以遍历dp[0][i]=i; 同理可得，dp[j][0]=j;
4)遍历顺序 由于递推顺序要从i-1 j-1去找i j的dp值所以递推也应该是从小到大，先算到i-1 j-1 ，再在此基础上找到i j*/
int main() {

    string word1,word2;
    cin>>word1>>word2;
   // cout<<word1.size()<<","<<word2.size()<<endl;
    int dp[word1.size()+1][word2.size()+1];//注意大小，最后返回值应该是dp[1.size()][2.size()]下标要取到size()值的，所以容量得+1
    for(int i=0;i<=word1.size();i++){dp[i][0]=i;}
    for(int j=0;j<=word2.size();j++){dp[0][j]=j;}
    for(int i=1;i<=word1.size();i++){
        for(int j=1;j<=word2.size();j++){
            if(word1[i-1]==word2[j-1]){dp[i][j]=dp[i-1][j-1];}
            else{
                dp[i][j]=min({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]})+1;
            }
        }
    }
    cout<<dp[word1.size()][word2.size()];
   return 0;
}
// 64 位输出请用 printf("%lld")