动态规划阶段总结之基础篇[必看].doc

动态规划阶段总结之基础篇by Zc序言动态规划是信息学竞赛中最重要的知识点之一，不仅思维难度高，而且变化多端，新思想新方法层出不穷，要求选手具有很强的创新思维和细腻的思考。这里基础篇从几个例题出发，向大家介绍几个动态规划中几种常见常用的模型，并简单介绍几种优化方法。正文【模型一】例题：数字三角形73 88 1 02 7 4 44 5 2 6 5(图1)图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。 注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。分析：这类问题一般比较简单，状态、阶段几乎是显而易见的，不过这也是动态规划中最基础最重要的几个概念，通过这样的例题，我们渐渐的能够认识到动态规划的本质。状态 ： 表示从顶部走到第i行第j个数字时最大的和是多少。方程 ：类似的例题还有NOIp2002普及组的过河卒、ZOJ 2271 Chance to Encounter a Girl、【模型二】例题：最长前缀 一些生物体的复杂结构可以用其基元的序列表示，而一个基元用一个大写英文字符串表示。生物学家的一个问题就是将一个这样的长序列分解为基元（字符串）的序列，对于给定的基元的集合P，如果可以从中选出N个基元P1，P2，Pn，将它们各自对应的字符串依次联接后得到一个字符串S，称S可以由基元集合P构成。在从P中挑选基元时，一个基元可以使用多次，也可以不用，例如，序列ABABACABAB可以由基元集合A,AB,BA,CA,BBC构成。字符串的前K个字符称为该字符串的前缀，其长度为K.请写一个程序，对于输入的基元集合P和字符串T，求出一个可以由基元集合P构成的字符串T的前缀，要求该前缀的长度尽可能的长，输出其长度。分析：这是一类非常基础的线性模型，一般都是一维的状态，其基本的方程形式为，W(i,j)为转移函数。状态 ：表示长度为i的前缀最少由几个基元构成。方程 ： | 条件为Sj+1.i 为一个基元更复杂一点的就是二维的串模型，例如经典的LCS问题（最长公共序列）。其状态为表示A串的前i个字符和B串的前j个字符的LCS的长度为多少。方程 ：虽然方程变成了2维，但是其本质还是线性的模型，其方程形式可以描述为其经典例题有：LIS（最长不下降子序列）、ZOJ 2432 Greatest Common Increasing Subsequence、ZOJ 1792 Gap Punishment Aligment Problem、SGU 214 Weird Dissimilarity【模型三】例题：石子归并在一个圆形操场的四周摆放着N堆石子(N= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(=20).(!)选择一种合并石子的方案,使用权得做N1次合并,得分的总和最小;(2)选择一种合并石子的方案,使用权得做N1次合并,得分的总和最大;分析：这类问题是基础动态规划中较为复杂的一种，不过其方程更加突出了动态规划递归子问题的特点。状态 ：表示合并第i个到第j个石子的最小代价是多少，表示合并第i个到第j个石子的最大代价是多少。方程 ： 这个方程中体现的化归的思想非常重要，将当前大堆分成两小堆进行解决，以后的很多动态规划问题大多都是基于这种思想。其经典例题有：IOI98 Polygon、POI99 Mustter、ZOJ 1554 Folding、UVA 10003 Cutting Stick、SGU 273 Game Po【模型四】例题：01背包问题我个人在感觉上觉得01背包这个模型其实和线性模型是非常相似的，但作为一个经典的模型，我还是把他独立出来了设n个重量为（W1,W2,.Wn）的物品和一个载重为S的背包，每个物品只能选择放或不放，将物品放进背包中的利润是Pi，问如何选择物品的种类和数量，使得背包获得最大的利润？分析：其实背包问题在理论上是NP问题的，当其背包的权值没有限制时是无法解决的，只有当权值较小时，才可以使用动态规划解决。状态 ：表示放入前i个物品且总重量不超过j时能获得的最大利润方程 ： 其经典例题有：ZOJ 1743 Concert Hall Scheduling、原创试题吃夜宵【模型五】例题：数的拆分给定一个整数N，现在要把n分解成若干个整数的和，且分解出的整数不可重复，求总共的分解方案。分析：统计问题一直是动态规划问题的重要分支之一，而动态规划虽然高效，但当问题规模变得很大时，仍需要我们进行优化才能使动态规划发挥其应有的用处。这里结合这个问题提出一种非常简单的处理统计或最优问题的油画方法。状态 ： 表示将i分解且分解出的最大数字不超过j时分解的方案是多少。方程 ：这个方程是O(N3)的，但是它还是有非常大的优化空间的。注意到 两式相减得到综合得到优化后的方程为 经典例题 ：ZOJ 1234 Chopsticks、ZOJ 1524 Supermarket、ZOJ 2069 Greatest Least Common Multiple、ZOJ 2230 Fouriers Lines这里我们将决策集合列出，并和以前得到的结果进行比较寻找相似的集合并直接引用以前的结果，达到优化决策的目的。这里很幸运的，我们发现原状态数组中就是保存的决策集合，但是有的时候并没有这么巧的是，不过我们可以重新定义一个优化数组来保存决策的集合，并每次求出某个状态后用常数的时间来维护这个数组，以便达到优化常数甚至O(1)的决策。小结本文简单的介绍了动态规划中最基本也是最常用的6个模型，细心的读者已经注意到，本文介绍的动态规划中只粗略的列出了动态规划时状态的设置以及大致方程