編集距離 - メモ付き

Question

編集距離問題を解決しようとしていますが、呼び出しを繰り返さないように結果をキャッシュします。それは、サブ問題をマップに保存しようとする前に機能しましたが、現在は機能しなくなりました。私が作る電話は、「あなたはいない」と「あなたはしてはいけません」を比較すると、1を返します。明らかに間違っていますが、なぜですか？

using namespace std; 
int counter = 0; 

int match(char c1, char c2){ 
    c1 == c2 ? 0 : 1; 
} 

int edit_distance(string s1, string s2,map<pair<string,string>, int>& memo){ 
    if(memo[make_pair(s1,s2)]) 
    return memo[make_pair(s1,s2)]; 
    int i = s1.size(); 
    int j = s2.size(); 

    if(s1.empty()) 
    return memo[make_pair(s1,s2)] = 1 + j; 
    if(s2.empty()) 
    return memo[make_pair(s1,s2)] = 1 + i; 

    int opt[3]; 

    opt[0] = edit_distance(s1.substr(1), s2.substr(1),memo) + match(s1[i-1],s2[j-1]); 
    opt[1] = edit_distance(s1.substr(1), s2,memo) + 1; 
    opt[2] = edit_distance(s1, s2.substr(1),memo) + 1; 

    int min = opt[0]; 
    for(int i = 1; i < 3; i++){ 
    if(opt[i] < min) 
     min = opt[i]; 
    } 
    memo[ make_pair(s1,s2) ] = min; 
    return min; 
} 

int edit_distance_driver(string s1, string s2){ 
    map<pair<string,string>,int> memo; 
    return edit_distance(s1, s2, memo); 
} 

int main(){ 
    cout << edit_distance_driver("thou shalt not","you should not") << endl; 
} 

Answer 1

問題はここにある：

opt[0] = edit_distance(s1.substr(1), s2.substr(1),memo) + match(s1[i-1],s2[j-1]); 

あなたは最初文字なしで再帰していますが、最後文字を確認してください。それがあるべきようにするには、代わりに、最初の文字をチェックしてください

：次に

int match(char c1, char c2){ 
    return c1 == c2 ? 0 : 1; 
} 

your code prints 6 for those strings：

opt[0] = edit_distance(s1.substr(1), s2.substr(1),memo) + match(s1[0],s2[0]); 

、明らかmatchは何かを返す必要があります。