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

One of Optimal Dynamic Programming Algorithm Using Segment Tree

作　　者：邹玉金[1] 

机构地区：[1]浙江经贸职业技术学院,浙江杭州310018

出　　处：《软件工程师》2014年第12期15-16,共2页Software Engineer

基　　金：浙江省自然科学基金项目(编号:LQ13G02000物联网环境下基于情境感知的数据流挖掘模型研究)

摘　　要：动态规划是解决多阶段决策最优化问题的一种思想方法,也是ACM程序设计竞赛中常用的算法。本文首先讨论了动态规划的基本思想和解题步骤。但基本动态规划对于数据规模很大的问题,在解题过程中还是存在效率和占用空间非常大的问题,本文巧妙利用线段树优化动态规划,提高对大规模数据处理的方法和技巧,在线段树基础上利用树状数组合理地解决了动态规划占用大量内存的问题。Dynamic programming solves a way of thinking that many stages make policy and the optimum problem,which is often used in the ACM.This paper discusses the basic idea of the dynamic programming and problem-solving steps.There is still a very big problem of efficiency and space in the problem solving process using the basic dynamic programming method while processing large-scale data.Using segment tree optimizating dynamic programming problem cleverly,we can improve methods and techniques for large-scale data processing,and rationally solve the problem of dynamic programming running memory intensively by the tree array which based on the segment tree.

关 键 词：动态规划 数据结构 线段树 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]