Source code online books for professionals by professionals

Listing 8-8.  A Memoized Recursive Solution to the LCS Problem
def rec_lcs(a,b):                               # Longest common subsequence
    @memo                                       # L is memoized
    def L(i,j):                                 # Prefixes a[:i] and b[:j]
        if min(i,j) < 0: return 0               # One prefix is empty
        if a[i] == b[j]: return 1 + L(i-1,j-1)  # Match! Move diagonally
        return max(L(i-1,j), L(i,j-1))          # Chop off either a[i] or b[j]
    return L(len(a)-1,len(b)-1)                 # Run L on entire sequences
 
This recursive decomposition can easily be seen as a dynamic decision process (do we chop off an element from 
the first sequence, from the second, or from both?), which can be represented as a DAG (see Figure 
8-5
). We start in 
the node represented by the full sequences, and we try to find the longest path back to the node representing two 
empty prefixes. It’s important to be clear about what the “longest path” is here, though—that is, what the edge weights 
are. The only time we can extend the LCS (which is our goal) is when we chop off two identical elements, represented 
by the DAG edges that are diagonal when the nodes are placed in a grid, as in Figure 
8-5
. These edges, then, have a 
weight of one, while the other edges have a weight of zero.

---

Chapter 8 
■
 tangled dependenCies and MeMoization 
177
For the usual reasons, you may want to reverse the solution and make it iterative. Listing 8-9 gives you a version 
that saves memory by keeping only the current and the previous row of the DP matrix. (You could save a bit more, 
though; see Exercise 8-13.) Note that cur[i-1] corresponds to L(i-1,j) in the recursive version, while pre[i] and 
pre[i-1] correspond to L(i,j-1) and L(i-1,j-1), respectively.