最短编辑距离

• 集合： 所有将 a[1~i] 变成 b[1~j] 的操作方式。

• 

• 首先初始化

for (int i = 0; i <= n; i ++ ) f[i][0] = i;
for (int i = 0; i <= m; i ++ ) f[0][i] = i;

很容易想到，如果一个字符串长度为0，那么想要达到和另外一个字符串相等，需要操作 i 次，加上 i 个字符。

• 可以想到，从 f[i - 1][j] 和 f[i][j - 1] 变成 f[i][j] 都只需要增加一个字母（操作1次）即可。因此 f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1 。

• 如果 a[i] 和 b[j] 相等的话，说明 f[i][j] 与 f[i - 1][j - 1] 相等。而如果不等的话，说明需要改变一个字符。因此

if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);

• 以上思路总结代码如下

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
  scanf("%d%s", &n, a + 1);
  scanf("%d%s", &m, b + 1);

  for (int i = 0; i <= m; i ++ ) f[0][i] = i;
  for (int i = 0; i <= n; i ++ ) f[i][0] = i;

  for (int i = 1; i <= n; i ++ )
      for (int j = 1; j <= m; j ++ )
      {
          f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
          if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
          else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
      }

  printf("%d\n", f[n][m]);

  return 0;
}