问题背景�

假设观测序列为y1,y2,y3，隐含序列为x1,x2,x3,
其中x1->y1为输出概率，x1->x2为转移概率。
设xij表示xi状态时可能的取值中的某一个值，即状态xi下的第j个值。
x的每个状态都有各自的取值，如果要求出最终状态的最大的概率值（最短路径），则需要n1n2n3...次计算。

算法思想

状态xi到状态xi+1，不用计算xi之前的概率，只需计算当前xi到xi+1，也就是ni*n(i+1)种可能。
看着里吧：
https://zh.wikipedia.org/wiki/%E7%BB%B4%E7%89%B9%E6%AF%94%E7%AE%97%E6%B3%95