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

#include <iostream>
#include <vector>
using namespace std;

int main(){
    // 编辑距离，字符串-->动态规划
    // 需要构建dp数组
    string word1,word2;
    cin>>word1>>word2;

    int n = word1.length();
    int m = word2.length();

    // 有一个字符串为空
    if(n*m == 0){
        cout<<m+n<<endl;
    }
    // dp数组
    vector<vector<int>> DP(n+1,vector<int>(m+1));
    // 边界状态初始化
    for(int i = 0; i < n+1; ++i){
        DP[i][0] = i;
    }
    for(int j = 0; j < m+1; ++j){
        DP[0][j] = j;
    }
    // 计算所有的dp值
    for(int i = 1; i < n+1; ++i){
        for(int j = 1; j < m+1; ++j){
            int left = DP[i][j-1] + 1;
            int down = DP[i-1][j] + 1;
            int left_down = DP[i-1][j-1];
            if(word1[i-1]!=word2[j-1]){
                left_down++;
            }
            DP[i][j] = min(left,min(down,left_down));
        }
    }
    cout<<DP[n][m]<<endl;
}