c++ - 最长公共(public)子序列算法的递归解的内存

当我尝试记忆最长公共(public)子序列问题的递归解时，记忆的soln返回不同的答案。我似乎不太清楚为什么...

#include <iostream>
#include <map>
#include <string>
#include <utility>
using namespace std;

string char_to_string(char c) { return string(1, c); }

map< pair<string, string>, string > hash;

// CORRECTED ANSWER AS PER DUKE'S SOLUTION - THANKS!
string lcsRec(string s1, string s2, string lcs = "") {
    pair<string, string> s1s2 = make_pair(s1, s2);
    pair< pair<string, string>, string> lcsTriplet = make_pair(s1s2, lcs);

    if (hash.count(lcsTriplet)) {
        return hash[lcsTriplet];
    }

    if (s1.size() == 0 || s2.size() == 0)
        return hash[lcsTriplet] = lcs;

    string s1Minus1 = s1.substr(0, s1.size() - 1);
    string s2Minus1 = s2.substr(0, s2.size() - 1);

     if (s1[s1.size() - 1] == s2[s2.size() - 1])
        return hash[lcsTriplet] = lcsRec(s1Minus1, s2Minus1, char_to_string(s1[s1.size() - 1]) + lcs);

    string omits1 = lcsRec(s1Minus1, s2, lcs);
    string omits2 = lcsRec(s1, s2Minus1, lcs);

    return hash[lcsTriplet] = (omits1.size() > omits2.size()) ? omits1 : omits2;
}

// MEMOIZED SOLUTION
string lcsRec(string s1, string s2, string lcs = "") {
    pair<string, string> p0 = make_pair(s1, s2);

    if (hash.count(p0)) return hash[p0];

    if (s1.size() == 0 || s2.size() == 0)
        return hash[p0] = lcs;

    string s1Minus1 = s1.substr(0, s1.size() - 1);
    string s2Minus1 = s2.substr(0, s2.size() - 1);

     if (s1[s1.size() - 1] == s2[s2.size() - 1])
        return hash[p0] = lcsRec(s1Minus1, s2Minus1, char_to_string(s1[s1.size() - 1]) + lcs);

    string omits1 = lcsRec(s1Minus1, s2, lcs);
    string omits2 = lcsRec(s1, s2Minus1, lcs);

    return hash[p0] = (omits1.size() > omits2.size()) ? omits1 : omits2;
}

// NON-MEMOIZED SOLUTION
string lcsRec(string s1, string s2, string lcs = "") {
    if (s1.size() == 0 || s2.size() == 0)
        return lcs;

    string s1Minus1 = s1.substr(0, s1.size() - 1);
    string s2Minus1 = s2.substr(0, s2.size() - 1);

     if (s1[s1.size() - 1] == s2[s2.size() - 1])
        return lcsRec(s1Minus1, s2Minus1, char_to_string(s1[s1.size() - 1]) + lcs);

    string omits1 = lcsRec(s1Minus1, s2, lcs);
    string omits2 = lcsRec(s1, s2Minus1, lcs);

    return (omits1.size() > omits2.size()) ? omits1 : omits2;
}

int main() {
    // cout << lcsRec("ooappleoot", "motot") << endl;
    // hash.clear();
    // cout << lcsRec("hello", "hello") << endl;
    // hash.clear();
    cout << lcsRec("hhelloehellollohello", "hellohellok") << endl;

    // for(map< pair<string, string>, string >::iterator iter = hash.begin(); iter != hash.end(); ++iter) {
    //     cout << iter->first.first << " " << iter->first.second << " " << iter->second << endl;
    // }
}

最佳答案

这里的问题是返回值取决于lcs参数，而不仅仅是s1和s2。

因此，lcsRec(s1, s2, A)将返回与lcsRec(s1, s2, B)(带有A != B)不同的值，但是您将它们视为相同。

一种想法是将lcs值与返回值分开，该返回值只是s1和s2的LCS，而忽略lcs(那么您可能需要一个辅助调用函数来将它们放在顶层)。这可能可以通过传递引用来完成，请小心，因为您不希望第一次调用lcsRec(在其中设置omits1)来更改将在第二次调用中使用的lcs值(其中您设置了omits2)。

关于c++ - 最长公共(public)子序列算法的递归解的内存，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21011772/