维特比算法

比如我们想输入“万里长城永不倒”：

深度优先搜索的话重复次数太多。

 

穷举法（遍历）：每条路径需要计算4次加法，共3×3×3=27条路径，共4×27=108次计算。 

维特比算法需要多少次计算？〔原文〕

维特比算法由安德鲁·维特比(Andrew Viterbi)于1967年提出。他是南加州大学博士，高通公司联合创始人、首席科学家，IEEE Fellow. 1991年获香农奖，2008年获美国国家科学奖章。