/*
/*
Let x and y be two strings over some finite alphabet A. We would like to transform x into y allowing only operations given below:
Deletion: a letter in x is missing in y at a corresponding position.
Insertion: a letter in y is missing in x at a corresponding position.
Change: letters at corresponding positions are distinct
Certainly, we would like to minimize the number of all possible operations.
Illustration
A G T A A G T * A G G C
| | | | | | |
A G T * C * T G A C G C
Deletion: * in the bottom line
Insertion: * in the top line
Change: when the letters at the top and bottom are distinct
This tells us that to transform x = AGTCTGACGC into y = AGTAAGTAGGC we would be required to perform 5 operations (2 changes, 2 deletions and 1 insertion). If we want to minimize the number operations, we should do it like
A G T A A G T A G G C
| | | | | | |
A G T C T G * A C G C
and 4 moves would be required (3 changes and 1 deletion).
In this problem we would always consider strings x and y to be fixed, such that the number of letters in x is m and the number of letters in y is n where n ≥ m.
Assign 1 as the cost of an operation performed. Otherwise, assign 0 if there is no operation performed.
Write a program that would minimize the number of possible operations to transform any string x into a string y.
Input
The input consists of the strings x and y prefixed by their respective lengths, which are within 1000.
Output
An integer representing the minimum number of possible operations to transform any string x into a string y.
Sample
Inputcopy
10 AGTCTGACGC
11 AGTAAGTAGGC
Outputcopy
4
*/
#include<iostream>
using namespace std;
char a[1010]={0},b[1010]={0};
int len1=0,len2=0,len3=0,i=0,m,n;
int dfs(int w,int e){
if(b[e]=='\0') return m-w; //如果b[]中所有字母都匹配了，删除a[]中剩下的字母
if(a[w]=='\0') return n-e; //如果a[]中所有字母都匹匹配了，插入b[]中还未匹配的字母
for(;w<m&&e<n;w++,e++){ //a[w]与b[e]都为'\0'时，结束循环
if(a[w]==b[e]) {
continue; //如果相等，继续循环向前
}
else{
len1=dfs(w,e+1)+1; //插入
len2=dfs(w+1,e)+1; //删除
len3=dfs(w+1,e+1)+1; //转换
if(len1<=len2 && len1<=len3) return len1;
else if(len2<=len1 && len2<=len3) return len2; //返回len1,len2,len3中的最小值
else return len3;
}
}
}
int main(){
cin>>m;
for(i=0;i<m;i++) cin>>a[i];
cin>>n;
for(i=0;i<n;i++) cin>>b[i];
cout<<dfs(0,0);
return 0;
}
（1）for循环不是所有的代码段都有返回值，比如 ，输入的2个字符串 都是3 AAA，你这个代码只会执行continue语句，最后没有返回值
（2）漏判了 a[w]和b[e]同时到达字符串终点的情况。
代码做了下修改
#include <iostream>
using namespace std;
char a[1010] = { 0 }, b[1010] = { 0 };
int dp[1010][1010] ;
int len1 = 0, len2 = 0, len3 = 0, i = 0,j, m, n;
#define INT_MAX 999999999
int dfs(int w, int e) {
if (b[e] == '\0' && a[w] == '\0') return 0;
else if (b[e] == '\0') { dp[w][e] = m - w; return m - w; } //如果b[]中所有字母都匹配了，删除a[]中剩下的字母
else if (a[w] == '\0') { dp[w][e] = n - e; return n - e; } //如果a[]中所有字母都匹匹配了，插入b[]中还未匹配的字母
else
{
if (dp[w][e] != INT_MAX)
return dp[w][e];
if (a[w] == b[e])
dp[w][e] = dfs(w + 1, e + 1);
len1 = dfs(w, (e + 1)) + 1; //插入
dp[w][e] = len1 < dp[w][e] ? len1 : dp[w][e];
len2 = dfs((w + 1), e) + 1; //删除
dp[w][e] = len2 < dp[w][e] ? len2 : dp[w][e];
len3 = dfs((w + 1), (e + 1)) + 1; //转换
dp[w][e] = len3 < dp[w][e] ? len3 : dp[w][e];
return dp[w][e];
}
}
int main() {
cin >> m;
for (i = 0; i < m; i++) cin >> a[i];
cin >> n;
for (i = 0; i < n; i++) cin >> b[i];
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
dp[i][j] = INT_MAX;
cout << dfs(0, 0);
return 0;
}
代码没粘全啊，重新粘
您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！