动态规划算法

算法基本思想：

• 将复杂问题分解为若干子问题
• 先求解子问题，重复利用子问题的解求得原问题的解

基本要素：

• 最优子结构性质
• 重叠子问题

基本步骤：

建立状态转移方程 -> 存储并复用之前的结果 -> 自底向上求解

应用：

条件随机场(CRF)
概率无向图模型、判别模型
常用于序列标注任务的推理层

序列标注：给定输入X=<x1,x2,x3,...xn> 给出对应的标注Y=<y1,y2,y3,...yn> y∈{tag|有限的标签种类}
推理层：学习状态转移参数/解

总结：

• 动态规划算法可以降低时间复杂度，代价为提高了空间复杂度
• 可以找到全局最优解
• 如何分解为可以被重复调用的子问题（找到状态转移方程）是难点