1Understand
The idea
For two sequences, dp[i][j] is the answer for the prefixes a[:i] and b[:j]. If the last characters match, extend dp[i−1][j−1]; otherwise take the best of dropping one character from either side. Edit distance, LCS and their variations differ only in that transition.
Intuition
For two sequences, dp[i][j] is the answer for prefixes a[:i] and b[:j]. If the last characters match, extend dp[i-1][j-1]; otherwise take the best of dropping from either side.
Edit distance, LCS and related problems differ mainly in the cost of that transition. Fill by increasing i,j so smaller prefixes are ready.
This is not the same as substring DP (contiguous), subsequence allows skips.
What you will be able to do
- Use prefix-length indices (i-1 for characters)
- Know the O(n log n) LIS trick
When to use it
- Longest increasing / common subsequence
- Minimum edits to transform strings
- Two strings compared prefix by prefix
2See it
Walkthrough
LIS length
nums = [10, 9, 2, 5], dp[i] = best ending at i.
1 / 5
Each dp[i] starts at 1 (the element alone).
Live template
Line 1 active
Complexity: time O(n·m), space O(n·m) → O(m)
Time and space O(n·m); space can drop to O(min(n,m)) with two rows. Recursive without memo is exponential. For only length of LCS you do not need the string reconstruction table.
Read the walkthrough as text
Edit distance. word1 = "horse", word2 = "ros".
dp[0][j] = j,dp[i][0] = i(insert/delete all).- At
hvsr: replace → from diagonal + 1. - Continue; when
smatchess(in horse vs ros), diagonal carries without cost. - Final
dp[5][3] = 3(replace h→r, delete o/e appropriately, classic answer 3).
LCS uses +1 on match and max on mismatch instead of min of edit ops.
3Recognise it
Kinds of problems (6)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Longest increasing subsequence
Example. LIS length in O(n log n).
How. Patience piles: binary search placement position for each x; or O(n²) table.
Longest common subsequence
Example. LCS of two strings.
How. dp[i][j] = +1 if match else max(dp[i-1][j], dp[i][j-1]) on prefixes.
Edit distance
Example. Minimum insert/delete/replace to match strings.
How. Same 2D table: match diagonal, else 1 + min of three neighbours.
Distinct subsequences
Example. Count s subsequences equal to t.
How. If s[i]==t[j]: dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; else carry dp[i-1][j].
Interleaving strings
Example. Is s3 an interleave of s1 and s2?
How. dp[i][j] whether s1[:i] and s2[:j] can form s3[:i+j].
Pattern matching with wildcards (regex, wildcard)
Example. Match pattern with * and ? wildcards.
How. 2D boolean DP: ? matches one char; * matches empty or extend.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Index shift
Why it happens. dp[i] lines up with s[i] mentally.
How it fails. LCS uses a[i] when dp[i] meant prefix length i, off-by-one on first character.
Fix. dp[i][j] is prefixes a[:i] and b[:j]; compare a[i-1] and b[j-1].
Substring vs subsequence
Why it happens. Contiguous vs skipping chars is an easy miss in the problem statement.
How it fails. Longest common substring DP allows gaps, reports subsequence length.
Fix. Substring DP resets on mismatch; subsequence allows max of skip-left/skip-up.
Empty prefix row
Why it happens. Main double loop can run from 0.
How it fails. Edit distance without dp[0][j]=j base, first row undefined, costs wrong.
Fix. Zero-th row/column encode empty-prefix costs before nested loops.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.