动态规划入门讲解

《动态规划入门讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划入门讲解by张惜今引入我们用一个简单的例子来让大家了解什么是动态规划灵梦的灵符博丽灵梦是东方幻想乡中博丽神社的巫女，她跟幻想乡中最老资格的妖怪八云紫一起维护着隔绝幻想乡与现实世界的大结界，维护现实世界不被幻想乡中的妖怪侵害，幻想乡中的生物也可以自由自在的维持古老的生活方式。但不幸的是，每隔六十年，结界会有一次大异变，为了维护结界的完整，博丽灵梦必须将灵力注入灵符，让灵力以最好的方式游走来修复结界。灵梦的灵符是一个三角形，由一堆数字组成，每个数字表示灵力经过这个位置获得的修复值，三角形共n层，第i层有i个数字，从上方的最尖端注入灵力，灵力只

2、能前往前位置的左下方或者右下方，最终走的下面的边的某个位置释放，问灵梦最多可以获得多少修复值？灵梦的灵符（USACO1.5.1）最容易想到的方法：回溯法我们可以列举每一条可能的路线，分别累加比较每条路线的修复值进行比较，取得最大的一条作为答案。我们先不引入时间复杂度的计算，来用一个n较小的例子手工计算我们需要做的计算量。为什么会计算那么多次呢？因为这个算法有天然呆的属性，多次经过同一个点，太健忘了！到这个点为止的最大和其实已经算出来了，而回溯法在每次回溯时会重复计算！这样要计算多少次？我们先不引入时间复杂度的计算，来用一个n较小的例子手工计算我们

3、需要做的计算量。n＝＝4，共有2^(4-1)＝8条路线每条两次加法和一次比较，共24次计算。但是如果n=100呢？n=1000呢？指数级的运算量将会飞快增长无法接受换一种方法取当前和较大的一种路线记录下来，往下走的时候直接用这个数跟下面点的修复值相加。每一层都看做一个这样的问题，也就是到当前位置可以获得的最大值，依次类推。原问题答案：到最下面某个位置（也就是最后一层子问题的［当前位置］）的最大修复值。这就是传说中的：动态规划这样的计算次数进行1次比较和1次加法（1+4）*4/2-1=9个点共计算18次。虽然只少了6次，但n增长时与n^2成正比的计

4、算量就可以接受了。动态规划的定义动态规划是：运筹学的一个分支解决策过程最优化的数学方法把多阶段过程转化为一系列单阶段问题动态规划——求解可以划分阶段的最优化问题的方法效率高局限性必须可以划分阶段并满足几个条件指数级->多项式级动态规划的适用条件不是一个纯理论的知识看出来这个题题是考用动态规划求解感性的认识1.最优子结构当前取得了最优值,那么直接用这个值来参与计算后面的状态能使后面的也最优只要比较取一个值最优的保存2.无后效性当前作出决策只会影响后面的状态前面的决策的影响都在状态中被包含了顺序3.重叠子问题也就是有前所述的那种重复计算的减少,动态规

5、划才能减少算法的运行时间动态规划的要素阶段状态决策阶段每个状态属于一个阶段有了前后关系保证最优子结构和无后效性比较明显,是前提也是一种特征比如：时间的前后，灵梦的灵符那种层次关系状态动态规划时操作的对象表示我们解到了哪一个子问题1维或者多维所属的阶段，一些相关信息决策是前面阶段的状态向后面的状态转移的操作是决策把各个阶段的状态依次求出动态规划的求解模式和程序实现划分阶段设计状态确定决策写出转移写出方程和边界递推：看作递推方程，用循环依次递推出每一个状态记忆化搜索：按搜索的方式写，但是对于已经搜索过的状态直接返回最优值，不再次搜索按照方程的形态大致

6、分类的几个例题线性选择背包问题区间DPTreeDP空的裂解原子核（POJ1887）灵乌路空有着特别姿态的鸦。左足是“分解之足”、右足是“融合之足”、还有制御两者的右手“第三足”，她以这三足操控著究极的能源。空居住在地灵殿在无聊的时候经常控制原子核进行核裂解来练习自己的能力。她捕捉到了N个原子核，控制每个原子核进行裂解会获得Ci的能量值，她可以依次挑选一个序列进行裂变（不必连续）。但是由于她能力的特殊性，她用来裂解的原子核的能量只能越来越低，否则会导致控制失败而造成核反应制御不能的后果。但是空是一个低智力的笨蛋，她想让你帮忙计算她最多可以控制几个原

7、子核进行裂变。分析经典的LIS模型，也就是线性选择型的DP阶段：按顺序处理到哪一个原子核状态:f[i]表示处理到第i个，且选取第i个的最大序列长度决策：上一个原子核是哪一个（逆推）方程f[i]=max(f[j])+11<=j

8、。分析阶段：物品随意排列，以做决定到了哪个物品作为阶段状态：f[i][j]表示处理到第i个物品，已经使用重量j得到的最大知识值决策与转移