LCS algorithm can also be implemented in a bottom-up fashion. That is, we can start from the simplest subproblem and build up the solution by progressively solving bigger problems. Instead of a hash-table we use a 2D array (2D as we would be tracking the lengths of sequences seen so far in the two input strings).

Suppose we are given two strings s1 and s2 of lengths m and n respectively. The base case corresponds to one of the strings being empty, in which case we do not have any common subsequence and just return 0.

int lookup[m+1][n+1];
for (int i = 0; i <= m; i++)
  lookup[i][0] = 0;
for (int j = 0; j <= n; j++)
  lookup[0][j] = 0;

We would use the above solutions (to the smallest subproblems) to progressively scan the two strings s1 and s2 looking which characters are matching, very similar to the approach seen previously.

Putting it together,

int lcs_dp(std::string s1, std::string s2, int m, int n)
{
  int lookup[m+1][n+1];

  for (int i = 0; i <= m; i++)
    lookup[i][0] = 0;
  for (int j = 0; j <= n; j++)
    lookup[0][j] = 0;

  for (int i = 1; i <= m; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      if (s1[i-1] == s2[j-1])
        lookup[i][j] = lookup[i-1][j-1] + 1;
      else
        lookup[i][j] = std::max(lookup[i-1][j], lookup[i][j-1]);
    }
  }
  return lookup[m][n];
}