Longest Common Subsequence

	PRINT-LCS(b, X, i, j)
1 if i = 0 or j = 0
2     then return
3 if b[i, j] = "↖"
4     then PRINT-LCS(b, X, i - 1, j - 1)
5          print xi
6 elseif b[i, j] = "↑"
7    then PRINT-LCS(b, X, i - 1, j)
8 else PRINT-LCS(b, X, i, j - 1)

For the b table in Figure 15.6, this procedure prints "BCBA." The procedure takes time O(m n), since at least one of i and j is decremented in each stage of the recursion.

Improving the code

Once you have developed an algorithm, you will often find that you can improve on the time or space it uses. This is especially true of straightforward dynamic-programming algorithms. Some changes can simplify the code and improve constant factors but otherwise yield no asymptotic improvement in performance. Others can yield substantial asymptotic savings in time and space.

For example, we can eliminate the b table altogether. Each c[i, j] entry depends on only three other c table entries: c[i - 1, j - 1], c[i - 1, j], and c[i, j - 1]. Given the value of c[i, j], we can determine in O(1) time which of these three values was used to compute c[i, j], without inspecting table b. Thus, we can reconstruct an LCS in O(m n) time using a procedure similar to PRINT-LCS.  Although we save Θ(mn) space by this method, the auxiliary space requirement for computing an LCS does not asymptotically decrease, since we need Θ(mn) space for the c table anyway.

We can, however, reduce the asymptotic space requirements for LCS-LENGTH, since it needs only two rows of table c at a time: the row being computed and the previous row. This improvement works if we need only the length of an LCS; if we need to reconstruct the elements of an LCS, the smaller table does not keep enough information to retrace our steps in O(m n) time.