POJ 3356 为算法导论原题简化版，这里只讲算法导论版编辑距离。
定义状态dp[i][j]表示将x[i……m]变为y[j……n]所需要的最小代价。
对于每一个状态，有6种操作，具体如下。
1、复制
功能：i + 1，j + 1
代价：cost1
2、替换
功能：i + 1，j + 1
代价：cost2
3、删除
功能：i + 1，j不变
代价：cost3
4、插入
功能：i不变，j + 1
代价：cost4
5、旋转
功能：i + 2，j + 2（前提是x[i] = y[j + 1]，x[i + 1] = y[j]）
代价：cost5
6、终止
功能：i = m + 1
代价：cost6
所以状态转移过程如下。
一、临界情况 j = n + 1
dp[i][j] = cost6
二、其余情况
if (x[i] == y[j] // 相等就执行复制操作
dp[i][j]= dp[i + 1][j + 1] + cost1
else // 不等就在剩余4种操作里选择一个代价最小的作为dp[i][j]
{
dp[i][j] = min(dp[i + 1][j + 1] + cost2, dp[i+ 1][j] + cost3, dp[i][j + 1] + cost4)
if (x[i] == y[j + 1] && x[i + 1]== y[j]) // 满足旋转条件就尝试旋转操作
dp[i][j]= min(dp[i + 2][j + 2] + cost5, dp[i][j])
}
算法的时间复杂度为 O(m * n)，空间复杂度为 O(m * n)。
本道题略有改变，不过大体思路一样。代码如下：
#include <cmath> #include <ctime> #include <cstdio> #include <string> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; const int MAX_SIZE = 1005; int dp[MAX_SIZE][MAX_SIZE]; int main() { //freopen("1.txt", "r", stdin); int lenx, leny; string x, y; while (cin >> lenx) { cin >> x >> leny >> y; memset(dp, 0, sizeof(dp)); for (int i = lenx; i >= 0; i--) for (int j = leny; j >= 0; j--) { if (i == lenx) dp[i][j] = leny - j; else if (j == leny) dp[i][j] = lenx - i; else { dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j + 1] + 1); dp[i][j] = min(dp[i + 1][j + 1] + 1, dp[i][j]); if (x[i] == y[j]) dp[i][j] = min(dp[i + 1][j + 1], dp[i][j]); } } printf("%d\n", dp[0][0]); } return 0; }
