Understanding the top down solution to the longest common subsequence problem

To find the longest common subsequence using a top-down dynamic programming approach, we translate the recurrence relation into a recursive function and use a memoization table to store results of subproblems that have already been solved.

The top down solution

As with any top-down solution, there is a recursive function that solves subproblems and a calling function that initializes the required data structures and triggers the computation. For the longest common subsequence, we define a single recursive function lcs and a calling function that invokes it for the full lengths of both strings.