title: Memoization of the recursive solution of Longest Common Subsequence Algorithm
body: <p>When I attempt to memoize the recursive solution of the Longest Common Subsequence problem, the memoized soln returns a different answer. I can't quite seem to figure out why ...</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;map&gt;
  #include &lt;string&gt;
  #include &lt;utility&gt;
  using namespace std;
  
  string char_to_string(char c) { return string(1, c); }
  
  map&lt; pair&lt;string, string&gt;, string &gt; hash;
  
  // CORRECTED ANSWER AS PER DUKE'S SOLUTION - THANKS!
  string lcsRec(string s1, string s2, string lcs = "") {
      pair&lt;string, string&gt; s1s2 = make_pair(s1, s2);
      pair&lt; pair&lt;string, string&gt;, string&gt; 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() &gt; omits2.size()) ? omits1 : omits2;
  }
  
  // MEMOIZED SOLUTION
  string lcsRec(string s1, string s2, string lcs = "") {
      pair&lt;string, string&gt; 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() &gt; 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() &gt; omits2.size()) ? omits1 : omits2;
  }
  
  int main() {
      // cout &lt;&lt; lcsRec("ooappleoot", "motot") &lt;&lt; endl;
      // hash.clear();
      // cout &lt;&lt; lcsRec("hello", "hello") &lt;&lt; endl;
      // hash.clear();
      cout &lt;&lt; lcsRec("hhelloehellollohello", "hellohellok") &lt;&lt; endl;
  
      // for(map&lt; pair&lt;string, string&gt;, string &gt;::iterator iter = hash.begin(); iter != hash.end(); ++iter) {
      //     cout &lt;&lt; iter-&gt;first.first &lt;&lt; " " &lt;&lt; iter-&gt;first.second &lt;&lt; " " &lt;&lt; iter-&gt;second &lt;&lt; endl;
      // }
  }
  </code></pre>