Наивный подход к самой длинной общей подпоследовательности

Question

Мы изучали теорию динамического программирования в течение осеннего квартала, и я пытаюсь освежить ее и продолжить изучение. Я в настоящее время пытается наивный подход к проблеме ЛВП, как упоминалось в этой статье TopCoder: Dynamic Programming

алгоритм выглядит следующим образом:

function LCS(S, T) 
    if S is empty or T is empty then 
     return empty string 

    if first char of S == first char of T then 
     return (first char of S) + LCS(S - first char, T - first char) 

    otherwise // first chars are different 
     return longer of LCS(S - first char, T) and LCS(S, T - first char) 

Например, если строки «ABCDE» и «DACACBE» , самая длинная общая подпоследовательность - «ACE».

Однако мои выходы действительны подстроки «ABE» вместо правильного «ACE». Что случилось с заказом моей реализации?

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


string LCS(string s, string t); 

int main(){ 
    string A = "ABCDE"; 
    string B = "DACACBE"; 
    cout << LCS(A,B) << endl; 
    return 0; 
} 

string LCS(string s, string t){ 

    string sSub = ""; 
    string tSub = ""; 
    if(!s.empty()) 
    sSub = s.substr(1); 
    if(!t.empty()) 
    tSub = t.substr(1); 

    if(s.empty() || t.empty()){ 
    return ""; // return an empty string if either are empty 
    } 

    if(s[0] == t[0]){ 
    string firstOfS = ""; 
    firstOfS += s[0]; 
    firstOfS += LCS(sSub, tSub); 
    return s[0] + LCS(sSub, tSub); 
    } 

    else{ 
    string a = LCS(sSub, t); 
    string b = LCS(s, tSub); 
    if(a.length() > b.length()){ 
     return a; 
    } 
    else{ 
     return b; 
    } 
    } 
} 

Answer 1

, как Фам сказал, что оба являются правильными, но если вы задаетесь вопросом, почему это происходит из-за последней части кода

else{ 
    if(a.length() > b.length()){ 
     return a; 
    } 
    else{ 
     return b; 
    } 
    } 

что, если a.length() = b.length() вы всегда возвращаете b. Такая же длина не означает, что они равны. вот почему у вас есть другой ответ, но правильный: