AlgoScope

Longest Common Subsequence

Match - diagonal + 1. Otherwise max of up and left. Trace back to recover the subsequence.

Dynamic programming, algorithm, intermediateAlso called LCS
Cell 1, 1 compares a with a and becomes 1.aceabcde0000010000
Cell 1, 1 compares a with a and becomes 1.aceabcde0000010000

String DP: LCS of abcde and ace

Decision, step 2 of 17

(1, 1): 'a' against 'a'. They match, so both prefixes end in a shared letter: diagonal 0 + 1 = 1.

Cost

Best
O(n * m)
Average
O(n * m)
Worst
O(n * m)
Space
O(n * m)

O(min(n, m)) space for length only.

Leads to

Topics that need this one first.

Taught by the same lesson

String DP covers these too, in the same run.