Algorithms
Edit Distance:Insert, Delete, Substitute as a Costed Grid
Levenshtein distance on a DP grid: insert, delete, substitute, and recover one alignment — related to LCS, a different job.
Read More#dynamic-programming
5 post(s)
Algorithms
LIS:Longest Increasing Subsequence in n log n
Longest increasing subsequence: the O(n²) best-ending-here table, then patience / tails plus binary search for n log n.
Read MoreAlgorithms
LCS:Longest Shared Subsequence Without Requiring Contiguous
Find the longest common subsequence of two strings with a DP grid: match or skip, then reconstruct one shared sequence.
Read MoreAlgorithms
Coin Change:Unbounded Combinations When the Item Can Repeat
Make change when each denomination may be used again: min-coins and count combinations, and why this is not 0/1 knapsack.
Read MoreAlgorithms
0/1 Knapsack:Pick or Skip When Each Item Exists Once
Fill a capacity with pick-or-skip DP: each item once, a 2D table or a 1D roll, and how to reconstruct which items went in.
Read More