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.

For the recurrence relations, if i < 0 or j < 0, the solution is 0, and this serves as the base case.

However, arrays cannot have negative indices. To handle this cleanly in the bottom-up table, we shift the meaning of i and j so that they represent the number of characters considered from each string rather than indices. This way, the base case becomes i == 0 or j == 0, which maps naturally to row 0 and column 0 of the table.

How does this shift change the recurrence?

The recurrence relation itself does not change. We still check whether the last characters match and either extend or exclude. The only difference is that when i represents the number of characters considered, the last character of the prefix is at index i - 1 in the string (instead of index i).

We can use i and j to denote the number of items considered from the start, instead of the index of the last item.