[LuoGu] P2758 编辑距离

(color{red}{mathcal{Description}})

设 (A) 和 (B) 是两个字符串。我们要用最少的字符操作次数，将字符串 (A) 转换为字符串 (B) 。这里所说的字符操作共有三种：

1、删除一个字符；

2、插入一个字符；

3、将一个字符改为另一个字符；

皆为小写字母

(color{red}{mathcal{Input Format}})

第一行为字符串 (A) ；第二行为字符串 (B)；

(color{red}{mathcal{Output Format}})

只有一个正整数，为最少字符操作次数。

(color{red}{mathcal{DataSize Agreement}})

字符串 (A) 和 (B) 的长度均小于(2000)

(color{red}{mathcal{Solution}})

考虑用dp

令 (dp[i][j]) 表示字符串 (A) 的前 (i) 位转换为字符串 (B) 的前 (j) 位需要最小的操作次数

再考虑状态的转移.这里有个小弯,其实操作一与操作二可以归为一个状态,因为仔细想想就知道没有区别.

所以得出状态转移方程

[dp[i][j]=egin{cases}dp[i-1][j-1]&(A[i]=B[j])\max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1&(A[i] eq B[j])end{cases} (1 leq i leq lengthA, 1 leq j leq lengthB) ]

初始化 (dp[i][0]=i),(dp[0][j]=j) ((1 leq i leq lengthA, 1 leq j leq lengthB))

(color{red}{mathcal{Code}})

#include <bits/stdc++.h>
#define LL long long
#define reg register

using namespace std;

const int kLen = 2e3 + 10;

int dp[kLen][kLen];
char A[kLen], B[kLen];

int main() {
  scanf("%s%s", A + 1, B + 1);
  int lena = strlen(A + 1), lenb = strlen(B + 1);
  for (reg int i = 1; i <= lena; ++i)
    dp[i][0] = i;
  for (reg int i = 1; i <= lenb; ++i)
    dp[0][i] = i;
  for (reg int i = 1; i <= lena; ++i)
    for (reg int j = 1; j <= lenb; ++j) {
      if (A[i] == B[j]) {
      	dp[i][j] = dp[i - 1][j - 1];
	  } else {
	  	dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
	  }
	}
  printf("%d
", dp[lena][lenb]);
  return 0;
}