2857. 编辑距离

//状态 dp[i][j]表示a的前i位变成b的前j位所要的最少时间
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[502][502];

string a, b;
int main() {
    int n;
    cin >> n;
    while (n--) {
        fill(dp[0], dp[0] + 502 * 502, 0);
        for (int i = 0; i < 502; ++i) {
            dp[i][0] = i;
            dp[0][i] = i;
        }
        cin >> a >> b;
        for (int i = 1; i <= a.size(); ++i) {
            for (int j = 1; j <= b.size(); ++j) {
                if (a[i - 1] == b[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        cout << dp[a.size()][b.size()] << endl;
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;


int main() {
    int N;
    cin >> N;
    while (N--) {
        string A, B;
        int ld[501][501];
        cin >> A >> B;
        for (int i = 0; i <= A.length(); i++) {
            ld[0][i] = i;
        }
        for (int i = 0; i <= B.length(); i++) {
            ld[i][0] = i;
        }
        for (int x = 1; x <= B.length(); x++) {
            for (int y = 1; y <= A.length(); y++) {
                if (A[y - 1] == B[x - 1]) {
                    ld[x][y] = ld[x - 1][y - 1];
                } else {
                    ld[x][y] = min(ld[x - 1][y], min(ld[x][y - 1], ld[x - 1][y - 1])) + 1;
                }
            }
        }
        cout << ld[B.length()][A.length()] << endl;
    }
    return 0;
}

}

#include<cstdio>
#include<cctype>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<utility>
#include<cassert>
#include<climits>
using namespace std;


int main()
{
#ifdef debug
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    int T;
    char str1[501], str2[501];
    scanf("%d", &T);
    unsigned editdistance[503];
    memset(editdistance, 0, sizeof(editdistance));
    while(T--)
    {
        scanf("%s%s", str1, str2);
        const unsigned size1 = strlen(str1);
        const unsigned size2 = strlen(str2);

        // When looking at the first char of str1.
        for(unsigned i = 1; i <= size2; i++)
            editdistance[i] = i;

        // Dynamic Programming
        for(unsigned i = 1; i <= size1; i++)
        {
            // Looking at the first char of str2
            editdistance[0] = i;
            unsigned ij = i - 1;
            for(unsigned j = 1; j <= size2; j++)
            {
                if(i - 1 < size1 && j - 1 < size2 && str1[i-1] != str2[j-1]) ij++;
                int a = min(min(editdistance[j-1], editdistance[j]) + 1, ij);
                ij = editdistance[j];
                editdistance[j] = a;
            }
        }
        printf("%u\n", editdistance[size2]);
    }
    return 0;
}