稀疏动态规划技术介绍

动态规划是一种有着广泛应用的算法设计思想。稀疏动态规划是一种在设计动态规划算法时通过利用数据稀疏性来提高算法效率的技术。该技术已经成功地用于计算生物学领域中的DNA序列比对和RNA二级结构预测。然而国内鲜见介绍稀疏动态规划的中文资料。发表在计算理论顶级期刊J.ACM上的文[3,4]是两篇稀疏动态规划研究方面的经典学术论文。本文介绍这两篇文章中的核心思想和关键技术。