D. Changing a String （编辑距离）（dp+记忆化）（dp后寻找路径大法）

D. Changing a String （编辑距离）（dp+记忆化）（dp后寻找路径大法）

题目链接：

​​i ] [ j ] 代表串A前i个变成串B前j个的最小花费。

dp后再倒着寻找路径就好了。好题啊。

AC代码：

#include #include #define N 1001using namespace std;int n, m, dp[N][N];char a[N], b[N];int main(){ scanf("%s%s", a, b); n = strlen(a), m = strlen(b); dp[0][0] = 0; for(int i = 1; i <= n; ++ i) dp[i][0] = i; for(int j = 1; j <= m; ++ j) dp[0][j] = j; for(int i = 1; i <= n; ++ i) for(int j = 1; j <= m; ++ j) { dp[i][j] = N; if(j && dp[i][j - 1] + 1 < dp[i][j]) // INSERT dp[i][j] = dp[i][j - 1] + 1; if(i && dp[i - 1][j] + 1 < dp[i][j]) // DELETE dp[i][j] = dp[i - 1][j] + 1; if(i && j && dp[i - 1][j - 1] + 1 < dp[i][j]) // REPLACE dp[i][j] = dp[i - 1][j - 1] + 1; if(i && j && a[i - 1] == b[j - 1] && dp[i - 1][j - 1] < dp[i][j]) dp[i][j] = dp[i - 1][j - 1]; } printf("%d\n", dp[n][m]); while(n > 0 || m > 0) //dp后再找路径 { if(m && dp[n][m - 1] + 1 == dp[n][m]) { printf("INSERT %d %c\n", n + 1, b[m - 1]); m --; continue; } if(n && dp[n - 1][m] + 1 == dp[n][m]) { printf("DELETE %d\n", n); n --; continue; } if(n && m && dp[n - 1][m - 1] + 1 == dp[n][m]) { printf("REPLACE %d %c\n", n, b[m - 1]); n --, m --; continue; } n --, m --; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。