Algorithm dossier
- Category: DP
- Worst-case complexity: O(n²)
- Approach: DP
- Data structure: Array
- First formalised: 1950s
Why this snippet is Coin Change
Why coin change DP. f[i] = fewest coins summing to i. Recurrence: f[i] = 1 + min(f[i - x] for x in c) (over denominations that fit). The base case f[0] = 0 is the empty sum. vs. greedy. Greedy (always take the largest coin that fits) works for canonical currencies (US, EUR) but *fails* on arbitrary denominations — c = [1, 3, 4], a = 6: greedy gives 4+1+1, DP gives 3+3.
How to read a redacted algorithm
Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.