Problem. You're climbing a staircase of n steps. Each move climbs 1 or 2 steps. In how many distinct ways can you reach the top?
n = 2 → 2 (1+1, 2)
n = 3 → 3 (1+1+1, 1+2, 2+1)
n = 5 → 8
The last move is either a 1 (from step n − 1) or a 2 (from step n − 2), and those two groups don't overlap, so ways(n) = ways(n − 1) + ways(n − 2): the Fibonacci recurrence. It's the smallest complete example of a DP: state, recurrence, base cases, order.
ML context. The same "count the ways to reach the end" DP counts how many ways a string can be segmented into vocabulary tokens (Change D), which is the denominator of a unigram tokenizer's probability model and the forward pass of segmentation lattices. Counting paths through a lattice (speech, CTC alignments) is this lesson with more edges.