記憶最長公共子序列算法的遞歸解決方案

Question

當我試圖記憶最長公共子序列問題的遞歸解決方案時，memoized 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; 
    // } 
} 

Answer 1

這裏的問題是，返回值取決於lcs參數，而不僅僅是s1和s2。

因此lcsRec(s1, s2, A)會從lcsRec(s1, s2, B)（與A != B）返回不同的值，但您對待它們是一樣的。

一個想法是將lcs值從返回值分開，只是被的s1和s2的LCS，忽略lcs返回值（那麼你可能需要一個幫手調用函數把它們放在一起在頂層） 。這可能可以通過引用來完成，但要小心，因爲您不希望第一次撥打lcsRec（您設置了omits1）來更改將在第二個電話中使用的lcs值（其中你設置了omits2）。

Answer 2

public static int len(String s1,String s2) { 
    int n=s1.length(); 
    int m=s2.length(); 

    int[][] a = new int[m][n]; 
    for(int i=0;i<m;i++) { 
     for(int j=0;j<n;j++) { 
      a[i][j]=0; 
      if(s1.charAt(j)==s2.charAt(i)) { 
       if(i==0 || j==0) 
        a[i][j]=1; 
       else 
        a[i][j]=a[i-1][j-1]+1; 
      }else { 
       if(i==0 && j==0) 
        a[i][j]=0; 
       else if(i==0) 
        a[i][j] = a[i][j-1]; 
       else if(j==0) 
        a[i][j] = a[i-1][j]; 
       else 
        a[i][j]=Math.max(a[i-1][j], a[i][j-1]); 
      } 
     } 
    } 

    /*for(int i=0;i<m;i++) { 
     for(int j=0;j<n;j++) { 
      System.out.print(a[i][j]+" "); 
     } 
     System.out.println(); 
    }*/ 
    return a[m-1][n-1]; 
} 

取消註釋上一個打印循環以更好地理解概念。 簡而言之：

a[i][j]=a[i-1][j-1]+1; // if s1[j] == s2[i] 
a[i][j]=Math.max(a[i-1][j], a[i][j-1]); // otherwise