21 lines
795 B
Plaintext
21 lines
795 B
Plaintext
Longest Common Subsequence: "ABCBDAB" and "BDCABA"
|
|
==================================================
|
|
|
|
- B D C A B A
|
|
- 0 0 0 0 0 0 0
|
|
A 0 0 0 0 1 1 1
|
|
B 0 1 1 1 1 2 2
|
|
C 0 1 1 2 2 2 2
|
|
B 0 1 1 2 2 3 3
|
|
D 0 1 2 2 2 3 3
|
|
A 0 1 2 2 3 3 4
|
|
B 0 1 2 2 3 4 4
|
|
|
|
length (bottom-right cell) = 4
|
|
reconstructed from the full table = "BCBA" (a valid subsequence of both strings)
|
|
two-row version = 4 (length only; cannot rebuild the string)
|
|
|
|
Calls made on two 15-character strings "ACGTTGCAACGTGCA" and "TGCATGCCGATGACG" (answer 9):
|
|
naive recursion -> 293086 calls
|
|
memoized -> 247 calls
|