Problem. A robot starts at the top-left cell of an m × n grid and can move only right or down. How many distinct paths reach the bottom-right cell?
m = 3, n = 7 → 28
m = 3, n = 2 → 3 (R D D, D R D, D D R)
Every path into cell (r, c) arrives from the cell above or the cell to its left, and those two groups are disjoint, so paths(r, c) = paths(r − 1, c) + paths(r, c − 1): lesson 12.2's recurrence on a grid.
ML context. A right-or-down path through an m × n grid is exactly a monotonic alignment between a sequence of length m and one of length n: each step either advances one sequence or the other. Dynamic time warping aligns two time series this way (lesson 12.8 minimises cost over these paths), CTC loss sums probabilities over alignments of audio frames to characters, and counting them shows why brute force over alignments is hopeless (Change D).