你体会过看了[普及-]题解还不会的恐惧嘛…
看来我还真是不会DP啊…

懵逼的 题目

传送至 Luogu

扯淡的 题解

f[i][j]拿A前i个字符转到B前j个字符的代价(记好了这个定义…要不然后面直接看不懂)
转移:

  • 相等: 直接等于f[i - 1][j - 1]没什么好说的
  • 不相等:
    • 改变: 把A[i]改成B[j], 等于f[i - 1][j - 1]也没什么好说的
    • 删除: 删掉了A[i] A[1 ~ i]变成了A[1 ~ (i - 1)], 所以是f[i - 1][j]
    • 插入: 插入了B[j]A[i]之前, 变成了f[i + 1][j], 且A[i] == B[j], 所以f[i + 1][j] == f[i + 1 - 1][j - 1]f[i][j - 1]

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#define MAXN (2000 + 5)
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int n;
int m;
string a, b;
int ans = 0;
int f[MAXN][MAXN];
int tmin(int, int, int);
void dp();
int main()
{
    cin >> a >> b;
    n = a.length();
    m = b.length();
    dp();
    printf("%d", ans);
    return 0;
}
void dp()
{
    memset(f, 0, sizeof(f));
    char xa[MAXN];
    char xb[MAXN];
    for (int i = 1; i <= n; i++)
        xa[i] = a[i - 1];
    for (int i = 1; i <= m; i++)
        xb[i] = b[i - 1];
    for (int i = 1; i <= n; i++)
        f[i][0] = i;
    for (int i = 1; i <= m; i++)
        f[0][i] = i;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (xa[i] == xb[j])
            {
                f[i][j] = f[i - 1][j - 1];
            }
            else
            {
                f[i][j] = tmin(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1;
            }
            //printf("%d %d: %d\n",i, j, f[i][j]);
        }
    }
    ans = f[n][m];
}
int tmin(int xx, int xxx, int xxxx)
{
    xx = min(xx, xxxx);
    return min(xx, xxx);
}

By 被beat的 Cansult