一道dp上手题。状态转移方程是（来自昊博士课件[Dynamic Programming.ppt]）
•如果计Ai和Bj是两个字符串的最后字符，计l[i,j]为字符串Ai和Bj最少的修改次数。
显然如果
Ai=Bj,有l[i,j]=l[i-1,j-1];
•否则l[i,j]=min(l[i-1,j],l[i,j-1],l[i-1,j-1])+1;
AC代码：
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
char str1[204], str2[204];
int len1, len2;
int p[204], n[204]; //上一行，当前行
int i, j; //控制str1，str2循环体变量
int main() {
// freopen("10411.in", "r", stdin);
str1[0] = '0', str2[0] = '0';
while (~scanf("%s%s", &str1[1], &str2[1])) {
len1 = strlen(str1), len1--; //去除str1[0]的干扰
len2 = strlen(str2), len2--; //去除str2[0]的干扰
for (j = 0; j <= len2; j++) p[j] = j; //当str1长度为0时
for (i = 1; i <= len1; i++) {
for (j = 0; j <= len2; j++) {
if (j == 0) n[j] = i;
else {
if (str1[i] == str2[j]) n[j] = p[j-1];
else n[j] = min(min(p[j-1], n[j-1]), p[j]) + 1; //等价于matrix[i][j]=min(min(matrix[i-1][j-1],matrix[i][j-1]),matrix[i-1][j])
}
}
for (j = 0; j <= len2; j++) { //数组滚动
p[j] = n[j];
}
}
printf("%d\n", n[len2]);
}
return 0;
}