Longest Common Subsequence of Two Sequences

Close to the previous problem, where we had to compute the minimum edit distance between two strings, here we have to get the maximum number of common elements in the same order between two sequences.

The similarity drives us to look again for a Dynamic Programming solution (adding up to the hint that these problems are in the same lot).

Here is my python solution:

def solution_dp(lhs, rhs):
    table = [[0] * (len(rhs) + 1)]  # 1
    for _ in range(1, len(lhs) + 1):
        table.append([0] * (len(rhs) + 1))

    for i in range(1, len(table)):
        for j in range(1, len(table[0])):  # 2
            if lhs[i - 1] == rhs[j - 1]:
                table[i][j] = table[i-1][j-1] + 1  # 3
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])  # 4
    return table[-1][-1]

1. The cache is created as in the previous problem, bidimensional, with extra dummy row and column to keep the code simple.
2. Again, we loop on all the "real" cells in the cache, from left to right, up to down.
3. The code change in the algorithm. If the corresponding elements in the input sequences match, we put as current value the counter stored in the top-left cell, increased it by one.
4. If it is a mismatch, we don't increase anything, just get the bigger value coming from the two possible alternatives.

And that's all. Richard Bellman, who found out this algorithm, was a genius.

Python script and testcase pushed to GitHub.