Longest Common Subsequence
Match - diagonal + 1. Otherwise max of up and left. Trace back to recover the subsequence.
String DP: LCS of abcde and ace
(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.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
String DP covers these too, in the same run.