DP：There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping subproblems. 是一种思想，避免重复计算，即子问题只计算一次，然后存储起来，利用空间换取时间，一般其目标式有累加的性质。

The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events, especially in the context of Markov information sources, and more generally, hidden Markov models. The forward algorithm is a closely related algorithm for computing the probability of a sequence of observed events. These algorithms belong to the realm of information theory.

即Viterbi 是一种DP算法，主要用于HMM

beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is an optimization of best-first search that reduces its memory requirements. Best-first search is a graph search which orders all partial solutions (states) according to some heuristic which attempts to predict how close a partial solution is to a complete solution (goal state). In beam search, only a predetermined number of best partial solutions are kept as candidates. Beam search uses breadth-first search to build its search tree. At each level of the tree, it generates all successors of the states at the current level, sorting them in increasing order of heuristic cost. However, it only stores a predetermined number of states at each level (called the beam width). 

区别：beam search 和DP的定义角度不同，beam search是一种启发式搜索，没有条件限制，都可以用，利用定义好的代价来剪枝，需要创建一个搜索树，因此每一个结点都与前面所有的父亲结点连接，生成很多结点在搜索树上，而DP是计算最优子问题的结果，保存在一个中间表中。

联系：如果beam search 解决的问题中也有最优子问题性质，那么其搜索树上的很多结点可以剪枝掉，即只是其父亲结点不同的那些结点可以只保留一个（即first prun，利用DP思想，只保留最优子问题，而所有子问题），那么其结果就是DP算法。从这个意义上说，DP是一种特殊的beam search，或者beam search应用范围更广，如果其应用的问题正好有最优子结构，那么其退化到DP （当然也可以进一步剪枝，即second prun）

关于复杂度，如果是bigram，那么DP的复杂度是O（n*k*k），O(n)是因为串长度为n，需要一步步走过去；O(k)是因为每一个中间问题有k个子问题（即每一个变量有k个状态），而每一个子问题找最优子问题时又需要向前看一步（因为bigram），那么又有k个结果，所以又是O（k）；类似，如果是trigram，那么其复杂度是O（n*k*k*k),因为每一步都有k*k个子问题，而又向前需要找k个子问题(x_i-1是参数)，实际上状态数变多了。

B_i[x_i-1,x_i]=D_i(x_i)+min_x_i-2(B_i-1[x_i-2,x_i-1]+V(x_i-2,x_i-1,x_i)).

另外：

1.However, when the overlapping problems are much smaller than the original problem, the strategy is called "divide and conquer" rather than "dynamic programming". This is why mergesort, quicksort, and finding all matches of a regular expression are not classified as dynamic programming problems. Note that the subproblems must be only slightly smaller (typically taken to mean a constant additive factor[citation needed]) than the larger problem; when they are a multiplicative factor smaller the problem is no longer classified as dynamic programming.

只用子问题规模来看的话，不是很好界定。比如mergesort（分为很多子问题，每个子问题进行排序，然后合并排序），这里感觉上和DP确实有点不同，但是又貌似满足DP的条件。（实际上其每个子问题是变化的，会产生新的子问题）

2. The Baum–Welch algorithm is a particular case of a generalized expectation-maximization (GEM) algorithm. It can compute maximum likelihood estimates and posterior mode estimates for the parameters (transition and emission probabilities) of an HMM, when given only emissions as training data.