贪心算法 动态规划 Viterbi算法
参考资料：https://www.bilibili.com/video/av37498689/?p=9
数学归纳法：如何从An推导出B，若把问题规模降低到0，即A0→B，同时若A0每增加一个元素，得到A1的变化过程即A1→A2，A2→A3......Ai→Ai+1，但存在的问题是Ai和Ai+1并不互为充要条件，随着i的增加，有价值的前提信息越来越少，为避免该问题，采用第二数学归纳法：{A1}→A2，{A1A2}→A3......{A1A2A3...Ai}→Ai+1
基本马尔科夫模型，即事物的状态只取决于它的前一个状态，就是贪心算法
高阶马尔科夫模型，即事物的状态取决于它之前的多个状态，即动态规划
其具有的特点：
- 动态规划和贪心算法都是根据A[0...i]计算A[i+1]的过程，其不需要后续的A[i+1],A[i+2]等数，一旦计算完成A[i+1],后续计算A[i+2],A[i+3]时均不会更改A[i+1]的值，即无后效性
- 无需知道A[0..i]是通过何种途径计算得到，只需知道他们当前状态值本身即可，若A[0..i]作为一个整体，则可认为动态规划就是马尔科夫过程，而非高阶马尔科夫过程。
Viterbi 算法
- 维特比算法是一个特殊但应用最广的动态规划算法，它是针对篱笆网络的有向图（Lattice）的最短路径问题而提出的。凡是使用隐含马尔可夫模型描述的问题都可以用维特比算法来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。
- 维特比算法的基础：如果概率最大的路径P（或叫最短路径）经过某个点，比如下图中的X22，那么这条路径上从起始点S到X22的这一段子路径Q，一定是S到X22之间的最短路径。否则，用S到X22的最短路径R替代Q，便构成了一条比P更短的路径，这显然是矛盾的。；从S到E的路径必定经过第i时刻的某个状态，假定第i时刻有k个状态，那么如果记录了从S到第i个状态的所有k个节点的最短路径，最终的最短路径必经过其中的一条。这样，在任何时刻，只需要考虑非常有限条最短路径即可。；结合上述两点，假定当我们从状态i进入状态i+1时，从S到状态i上各个节点的最短路径已经找到，并且记录在这些节点上，那么在计算从起点S到前一个状态i所有的k个结点的最短路径，以及从这k个节点到Xi+1，j的距离即可。
在每一个时刻，计算当前时刻落在每种隐状态的最大概率，并记录这个最大概率是从前一时刻哪个隐状态转移过来的，最后再从结尾达到最大概率的那个状态回溯，就可以得到最有可能的最优路径。