Problem. A hidden Markov model (HMM) has hidden states (tags), a probability of starting in each state, a probability of moving from each state to each other (transitions), and a probability of each state producing each word (emissions). Given a sentence, return the most likely tag sequence and its probability.
words: the dog walk
tags: DET NOUN VERB (most likely, probability ≈ 0.045)
"dog" could be a noun or a verb ("to dog someone"), and "walk" could be either too. Each word's best tag depends on its neighbours' tags, and those depend on theirs. But the model is Markov: a tag depends only on the previous tag. So the best path that ends in tag s at position t only needs the best paths ending in each tag at position t − 1. That's the DP.
ML context. Viterbi is the decoding step for every model that scores tag sequences with local transitions: HMM part-of-speech taggers, conditional random fields on top of neural encoders for named-entity recognition, and classic speech recognition, where states are phonemes and observations are audio frames. Lesson 12.10's forward algorithm is the same trellis with a sum in place of the max; together they cover "best explanation" and "total probability" of a sequence.