Dynamic Programming 2: Real Problems with Edit Distance, LCS and Knapsack
Two-dimensional DP tables hold prefixes of two strings or a budget: Levenshtein for "did you mean?", LCS for a diff that matches git diff's output, and 0/1 knapsack for budget-limited campaign selection. We write all three in C#, measure a 20x speedup from bounded Levenshtein, show the loop-direction trap in one-row knapsack, and close the series with a pattern decision table.
8 Nov 2026
·
14 min
·
2
