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.

The lcs function

The function lcs takes as input an index i into s1, an index j into s2, references to both strings s1 and s2, and a reference to the memoization array memo. The function returns the length of the longest common subsequence of the prefixes s1[0...i] and s2[0...j].

The memo array has dimensions m × n where m is the length of s1 and n is the length of s2, and is initialized with -1 in the calling function, where -1 indicates that the state has not yet been computed. Any non-negative value represents the computed length of the longest common subsequence for that pair of prefixes.