acwing 902.最短编辑距离

算法思路出处

#include <bits/stdc++.h>

using namespace std;

string s1 , s2 ;
int n , m ;

int main()
{
    cin >> n >> s1 >> m >> s2;
    //空串和非空串统一操作
    s1 = '#' + s1 ;
    s2 = '@' + s2 ; 

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

    cout << dp[n][m] ;

    return 0 ;
}