Understanding the bottom up solution to the longest common subsequence problem

To find the longest common subsequence 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

When implementing the recurrence relation using a top-down algorithm, i and j are indices into s1 and s2, and the base case occurs when either index drops below 0.