Two-dimensional Dynamic Programming
Harder two-sequence transitions
The same table as before, with transitions that need real care about what each branch means.
Key idea
Counting how many ways one sequence appears inside another
The state is the same pair of prefixes. The answer at (i, j) is how many ways the first j characters of the target appear as a subsequence within the first i characters of the source.
The transition splits on the last source character. It can always be ignored, which contributes the count at (i-1, j). If it matches the target's last character, it can also be used, which contributes the count at (i-1, j-1).
Both branches are added rather than maximized, because they are different ways rather than competing options. That is the difference from the earlier lesson and it is easy to carry over wrongly.
Why it works
The base column is ones, not zeros
Matching an empty target is achievable in exactly one way, by using nothing. Setting that column to zero makes every count collapse to zero, which is the same identity-element point as U14 and it bites harder here because the table is larger.
The base row, where the source is empty and the target is not, correctly stays at zero. Two edges of the table with different base values is normal and worth writing down before looping.
Key idea
Measuring how different two sequences are
A different question on the same table: the fewest single-character edits turning one sequence into another, where an edit inserts, removes, or replaces one character.
If the last characters match, nothing needs doing and the answer is the answer for both prefixes shortened. If they differ, one edit must happen and the three kinds correspond to the three neighbors.
Naming the three neighbors is the thing to get right, so here they are for one mismatching cell.
Why it works
Name each neighbor before writing the min
The three neighbors are not interchangeable, and knowing which is which matters as soon as a problem restricts the allowed operations. Diagonal is a replacement, up is a deletion from the first input, left is an insertion into it.
If a variant forbids replacement, drop the diagonal term. If insertions are free, its term loses the plus one. Writing the three out with those names attached makes such variants a one-line change instead of a rederivation.
Gotcha
Both base edges are non-zero here
Turning a prefix into nothing costs one deletion per character, so the base column counts up rather than being zeros. The base row counts up too, for insertions.
This is the most common error in this problem: initializing the table to zeros and starting the loops at one, which quietly claims that turning a five-character string into nothing is free. Fill both edges explicitly.
Cost
Cost
Both are one cell per pair of prefixes with constant work, so O(len(a) times len(b)) time and the same space, reducible to two rows.
The counting version's numbers can grow very large, and Python integers handle that without overflow. In a language with fixed-width integers the problem would normally specify a modulus, which is worth mentioning as a difference.
Predict the output: a zeroed base column
This counts appearances but initializes the whole table to zeros without setting the empty-target column. Type the two values it prints.
Distinct Subsequences
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Edit Distance
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.