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

//https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314?tpId=37&rp=1&ru=%2Fexam%2Foj%2Fta&qru=%2Fexam%2Foj%2Fta&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26pageSize%3D50%26search%3D48%26tpId%3D37%26type%3D37&difficulty=&judgeStatus=&tags=&title=52&gioEnter=menu

#include <iostream>

using namespace std;

int main() {
    string s1, s2;

    while(cin >> s1 >> s2){
        s1 = " "+s1;
        s2 = " "+s2;

        int n = s1.size();
        int m = s2.size();

        int dp[n][m];

        for(int i = 0;i<n;i++)
            dp[i][0] = i;

        for(int i = 0;i<m;i++)
            dp[0][i] = i;

        for(int i = 1;i<n;i++)
            for(int j = 1;j<m;j++){
                dp[i][j] = min(dp[i-1][j], dp[i][j-1])+1;
                if(s1[i]==s2[j])
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
                else
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1);

            }

        cout << dp[n-1][m-1];


    }

}