Since we remember the past, we know that we can try and remember intermediate computations of our recursive Longest Common Subsequence (LCS) algorithm we developed previously in order to reduce the cost of making several recursive calls. We can use a hash-table to remember the intermediate results.

Since we are looking at the lengths of two substrings while matching the characters, our intermediate results would be of the form int_result[i][j] for different lengths i and j of the two strings. Before we make our recursive calls, we just check the stored intermediate result to see if we have computed the LCS for the substring lengths.

In particular, we use an unordered_map and form a key (here, we use a string key) using the different lengths of strings m and n:

std::unordered_map<std::string, int> lookup;
std::string key = std::to_string(m) + ":" + std::to_string(n);

If the character we are analyzing matches, we update the key and increment our length counter.

lookup[key] = lcs_r(s1, s2, m - 1, n - 1) + 1;

If not, we make recursive calls including and excluding characters from the two strings (very similar to incl and excl we saw earlier) and compute the maximum of the two returned values (as we are computing the longest common subsequence).

lookup[key] = std::max(lcs_r(s1, s2, m - 1, n),
                       lcs_r(s1, s2, m, n - 1));

Putting it all together:

std::unordered_map<std::string, int> lookup;
int lcs_r(std::string s1, std::string s2, int m, int n)
{
  // base case
  if (m == 0 || n == 0)
    return 0;
  std::string key = std::to_string(m) + ":" + std::to_string(n);
  if (lookup.find(key) == lookup.end())
  {
    if (s1[m - 1] == s2[n - 1])
      lookup[key] = lcs_r(s1, s2, m - 1, n - 1) + 1;
    else
      lookup[key] = std::max(lcs_r(s1, s2, m - 1, n),
                             lcs_r(s1, s2, m, n - 1));
  }
  return lookup[key];
}

The time complexity of this solution is O(mn) with a space complexity of O(mn) to store the lookup table, where m and n are the lengths of the input strings.