解題思路：這道題的基本模型就是編輯距離的模型，只是多了一個路徑記錄的過程。

學習一下：http://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html

最開始把問題搞錯了，以為是兩個串都可以做修改，無論我怎么想都不通。

回到這個題目上，這道題和最長公共子序列很相似，思路可以說是一樣的，包括記錄路徑。

其實也就是根據遞推數組的結果來判斷。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 85; char A[maxn],B[maxn]; int dp[maxn][maxn],len1,len2;void path() {int tmp, i = len1, j = len2;int step = 0;while(i >= 1 || j >= 1){if(A[i-1] == B[j-1]) tmp = 0;else tmp = 1;if(dp[i][j] == dp[i-1][j-1] + tmp && i >= 1 && j >= 1){if(tmp)printf("%d Replace %d,%c\n",++step,i,B[j-1]);i--, j--;}else if(dp[i][j] == dp[i-1][j] + 1 && i >= 1){printf("%d Delete %d\n",++step,i);i--;}else if(dp[i][j] == dp[i][j-1] + 1 && j >= 1){printf("%d Insert %d,%c\n",++step,i+1,B[j-1]);j--;}} }int main() {while(scanf("%s %s",A,B)!=EOF){getchar();len1 = strlen(A);len2 = strlen(B);memset(dp,0,sizeof(dp));for(int i = 0; i <= len1; i++)dp[i][0] = i;for(int i = 0; i <= len2; i++)dp[0][i] = i;for(int i = 1; i <= len1; i++)for(int j = 1; j <= len2; j++){int tmp = min(dp[i][j-1],dp[i-1][j]) + 1;int d = A[i-1] == B[j-1] ? 0 : 1;dp[i][j] = min(tmp,dp[i-1][j-1]+d);}printf("%d\n",dp[len1][len2]);path();}return 0; }

總結

以上是生活随笔為你收集整理的hdu 1516(编辑距离+记录路径)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。