EOJ 2857 编辑距离
http://www.acm.cs.ecnu.edu.cn/problem.php?problemid=2857
一道典型dp,状态转移方程类似LCS。
操作有三种：1修改一个字母，2删除一个字母，3插入一个字母。
对于dp[i][j],能从如下状态转移而来：
if(a[i] == b[j])
不操作—— 对应状态dp[i-1][j-1];
else
操作1——a[i]改成b[j], 对应状态dp[i-1][j-1]+1;
操作2——删a[i], 对应状态dp[i-1][j]+1;
操作3——在a[i], a[i+1]间插入m，使 m = b[j], 对应状态dp[i][j-1]+1;
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 6 using namespace std; 7 8 int main() 9 { 10 int t; 11 scanf("%d", &t); 12 while(t--) 13 { 14 char a[505], b[505]; 15 scanf("%s%s", a, b); 16 int la = strlen(a), lb = strlen(b); 17 int dp[505][505]; 18 //memset(dp, 0x3f, sizeof(dp)); 19 20 for(int i=0; i<=la; i++) 21 dp[i][0] = i; 22 for(int j=0; j<=lb; j++) 23 dp[0][j] = j; 24 for(int i=1; i<=la; i++) 25 for(int j=1; j<=lb; j++) 26 if(a[i-1] == b[j-1]) 27 dp[i][j] = dp[i-1][j-1]; 28 else 29 dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1; 30 printf("%d ", dp[la][lb]); 31 } 32 }