一种基于线段树的动态规划优化算法

摘要

动态规划是解决多阶段决策最优化问题的一种思想方法,也是ACM程序设计竞赛中常用的算法。本文首先讨论了动态规划的基本思想和解题步骤。但基本动态规划对于数据规模很大的问题,在解题过程中还是存在效率和占用空间非常大的问题,本文巧妙利用线段树优化动态规划,提高对大规模数据处理的方法和技巧,在线段树基础上利用树状数组合理地解决了动态规划占用大量内存的问题。