Understanding the bottom-up solution to the longest palindromic subsequence problem

To solve the longest palindromic subsequence problem using a bottom-up dynamic programming approach, we fill a table iteratively beginning from the smallest subproblems and building towards the final answer. As with any bottom-up solution, we process subproblems in an order that guarantees every result we depend on has already been computed and stored before we need it.

The bottom up solution

Since a subsequence does not need to be contiguous, characters can be skipped as long as their relative order is preserved. Our goal is to compute, for each range s[i...j], the length of the longest palindromic subsequence contained within it.

We create a 2D integer array lps of dimensions n × n, where lps[i][j] stores the length of the longest palindromic subsequence within the substring s[i...j]. All entries are initialized to 0.

The lps array has a size n x n and is initialized with 0.

We then set lps[i][i] to 1 for all 0 <= i < n, since every single character is itself a palindromic subsequence of length 1. This serves as the base case.

What about entries where i > j?

These entries correspond to empty ranges (where the left index is past the right index), and they remain at their initialized value of 0 since an empty substring has no palindromic subsequence. We never write to these entries directly, but as we'll see, one of them is read during the length == 2 computation, and the 0 value there is exactly what we need.

lps[i][i] is set to 1 for 0 <= i < n as the base case.