一句话定义
维特比解码（Viterbi decoding）是一种动态规划（dynamic programming）算法，用于在一串随时间变化的状态序列中，找出总得分最高、或总代价最低的那一条完整路径。
为什么不能一条条试
设想给一句话做词性标注：每个词有几个候选标签，前后标签之间还有搭配偏好（形容词后面接名词，比接动词更常见）。如果句子有 20 个词、每个词 5 个候选，可能的标注序列就是 5 的 20 次方，逐条打分完全不现实。这就是"路径爆炸"。
维特比算法的关键观察是：整条路径的得分是一步步累加出来的，而"下一步能拿多少分"只取决于当前处在哪个状态，不取决于之前是怎么绕过来的。由此推出一个很强的结论——如果最终的最优路径在第 t 步经过了状态 A，那么它前面那一段，必然也是"从起点走到 A 的所有走法里最好的那一段"。否则把它替换掉，整条路径还能更优，矛盾。这就是所谓最优子结构。
打个比方：你开车从北京去上海，每天傍晚决定在哪个城市过夜。第二天怎么走，只跟今晚在哪有关，跟昨天绕了哪条路无关。所以不必记住全部走法，只需要对每个"可能的过夜城市"记下一条"到这里最省时的走法"。那些更慢的走法，后面无论怎么开都追不回来，直接扔掉。
算法于是变成从左到右逐列推进：每一步对每个状态只保留一条目前为止最好的来路（称为幸存路径），记录它的累计得分，其余统统丢弃；走到终点后，从终点往回倒推，就还原出整条最优路径。计算量从指数级降到与"序列长度 × 状态数平方"成正比。
和邻居们的区别
| 方法 | 保留什么 | 结果 |
|---|---|---|
| 暴力枚举 | 所有路径 | 精确最优，但指数级爆炸 |
| 逐步取最大（贪心） | 每步只留 1 条 | 快，但可能全局次优，甚至拼出不合法序列 |
| 维特比解码 | 每个状态各留 1 条幸存路径 | 精确最优，多项式复杂度 |
| 前向-后向算法 | 汇总全部路径的概率 | 得到每步的边缘概率，而不是一条路径 |
| 集束搜索（beam search） | 每步只留得分最高的 k 条 | 近似解，k 取到状态总数时即等价于维特比 |
一句话记忆：集束搜索的 k 开到"状态总数"，它就成了维特比。
同门师兄弟
维特比是动态规划家族的一员，同一套思想还出现在编辑距离、最长公共子序列、背包问题里：只要问题满足"最优子结构 + 重叠子问题"，就能用"每步只留最优、丢掉的一定翻不了盘"这个套路把指数级压成多项式级。
对从业者的意义
- 通信领域：卷积码译码，手机、卫星与深空链路的长期主力算法。
- 语音识别：隐马尔可夫模型时代的解码核心，如今 CTC 类模型的解码也常借用维特比思路。
- 自然语言处理：词性标注、分词、命名实体识别，尤其是条件随机场（CRF）层的推理，跑的就是维特比。
- 生物信息学：基因序列的比对与标注。
落到日常工程里：当模型输出是一串互相依赖的标签——这一格的答案会影响下一格的得分——逐格取最大值往往不是最优，甚至可能拼出不合法的序列。这时需要的是联合解码，而维特比就是其中最经典的那把刀。