递归的代码找不到错误

Question

/*
/*
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;
}

Answer 1

（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;
}