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.