Understanding the top-down solution to the longest palindromic subsequence problem

To solve the longest palindromic subsequence problem 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.

The lps function

The function lps takes as input a left index i, a right index j, a reference to the string s, and a reference to the 2D memoization array memo. The function returns the length of the longest palindromic subsequence within the substring s[i...j].

The memo array has dimensions n × n 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 palindromic subsequence for that range.