1、动态规划算法及算法思路的分析 石家庄二中 贾志豪- 1 -动态规划算法及算法思路的分析石家庄二中 贾志豪关键字动态规划 状态表示 状态转移 最优化原理 无后效性摘要在信息学竞赛中，我们经常遇到求最优解的问题。这些问题的特点是，只需要求出最优解，而不要求写出最优解的具体情况。为了解决这类问题，我们经常会用到一种有效的算法动态规划。使得我们可以在有限的时间内，求出问题的解。本文首先介绍一些关于动态规划的理论知识，然后将介绍向动态规划的思路上靠拢的方法即如何思考，最后再介绍一些经典例题。希望大家能互相促进。我的邮箱是： QQ：396511873目录一 动态规划的理论知识1.1 动态规划的基本思想1.
2、2 动态规划问题的特征1.3 使用动态规划的原则二 解题时的思路如何向动态规划上靠拢2.1 分析问题是否符合动态规划的原则2.2 确定使用动态规划时的状态和状态转移动态规划算法及算法思路的分析 石家庄二中 贾志豪- 2 -2. 3 估计程序的时间、空间复杂度及编程的难易程度三 一些经典例题四 习题正文一 动态规划的理论知识1.1 动态规划的基本思想动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的
3、解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 （本段文字摘自国家集训队论文）1.2 动态规划问题的特征动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子
4、问题重叠性质。动态规划算法及算法思路的分析 石家庄二中 贾志豪- 3 -1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。1.3 使用动态规划的原则符合最优化原理和无后效性原则是使用动态规划的原则。1、最优化原理：最优化原理一概念在刘汝佳的算法艺术与信息学竞赛一书中是这样解释的再把原问题转换成规模更小的字问题时，原问题最优当且仅
5、当子问题最优，这就是最优化原理。可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。2、无后效性原则：所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说， “未来与过去无关” ，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段 I 中的状态只能由之前的有限步状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就
6、是无后效性。动态规划算法及算法思路的分析 石家庄二中 贾志豪- 4 -在这里，特别要注意的是：对于某些不满足无后效性原则的状态表示，可以通过更改状态表示的维数（一般为增加数组维数） ，使得状态表示满足无后效性（这一点在后面的例题中会具体介绍） 。但不可避免的，在增加维数的同时，会增加问题的时间、空间复杂度。这就是在动态规划算法中的一个弊端。在这里，笔者要说的是，在某些情况下，动态规划并不一定是最好的算法，甚至不能算是一个较好的算法。希望读者在后面的问题中能用心体会。二 解题时的思路如何向动态规划上靠拢很自然的，大家在思考某一道题，会先考虑它能不能用动态规划解题，动态规划在这道题中是不是一个较优
7、的算法。而一部分人思考的过程是：这一道题如果我能想出状态表示和状态转移方程，那么它就可以使用动态规划，否则就不能。读到这里大家可能会笑，但大部分初学动态规划的人在思考问题时都会是这种思路。其实，动态规划在一道题中的价值有无、价值大小是有规律可循的。下面笔者就介绍一种较为行之有效的解题思路。1、 分析问题是否符合动态规划的原则2、 确定使用动态规划时的状态和转态转移、 估计程序的时间、空间复杂度及编程的难易程度首先：分析问题是否符合动态规划的原则在分析是否符合动态规划的原则，一般只分析问题的解是否符合最优化原理， （因为无后效性原则可以通过改变状态表示的维数来实现） 。动态规划算法及算法思路的分
8、析 石家庄二中 贾志豪- 5 -对于最优化原理，一般只分析问题的最优解是否可以通过局部最优解来实现。比如：如果我们能保证在前三个阶段我们的解是最优的，那么是否可以推出在第四个阶段我们的解依然最优。其次：确定使用动态规划时的状态和状态转移如果我们已经确定问题符合动态规划的原则，那么现在，我们就可以开始考虑如何实现动态规划。在考虑如何实现动态规划时，一般需要思考两个问题状态表示和状态转移。在思考状态表示时，就不得不去考虑无后效性问题了（笔者认为，在第一步中一般不过多的考虑无后效性问题） ，状态的表示一般用数组来实现，大多数情况下，数组的第一个下标用来表示执行到第几个阶段（有一些程序在最外层嵌套 F
9、or 语句除外） ，之后的几个下标用来表示用来实现无后效性。 （笔者建议，数组的维数最好不要超过维，因为维数过多会使重叠子问题变少，增加时间、空间复杂度和编程的难易度） 。在确定了状态表示后，我们的动态规划就实现了一半了。确定状态转移（方程） 。在确定了状态表示之后，就需要去确定状态转移方程（事实上，这两部是在同时进行的） 。在这里，笔者要提醒的是，状态转移方程必须要正确，因为状态转移方程失之毫厘，最后的结果就会差之千里（读者可以想一想递归树和递归方程） 。最后要提醒的是，某些人在使用动态规划时，经常回担心边界条件的正确与否，事实上，只要状态转移方程是对的，边界条件一般不会出错（有经验的读者会
10、深表赞同） 。动态规划算法及算法思路的分析 石家庄二中 贾志豪- 6 -最后：估计程序的时间、空间复杂度及编程的难易程度一位以上三个参量是评价算法在解决问题时的优劣标准。一般情况下，动态规划的空间复杂度近似于时限状态的数组大小，时间复杂度= 状态数 *决策数目*转移费用（刘汝佳观点） ，一般的，这个公式的结果为 O(n(1+状态数组维数 )；大家可想而知，大状态数组维数过多时，动态规划并不是一个很好的算法。对于编程复杂度，其参数值因题而异，在这里就不作介绍。三 一些经典例题1、货币系统（USACO Section 2.2 PROB: Money Systems）母牛们不但创建了他们自己的政府而
11、且选择了建立了自己的货币系统。In their own rebellious way,，他们对货币的数值感到好奇。传统地，一个货币系统是由 1,5,10,20 或 25,50, 和 100 的单位面值组成的。母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。举例来说, 使用一个货币系统 1,2,5,10,.产生 18 单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数将会适合 long long (C/C+) 和 Int64 (Free Pascal)。IN
12、PUT FORMAT动态规划算法及算法思路的分析 石家庄二中 贾志豪- 7 -货币系统中货币的种类数目是 V 。 (1=aji) do begindi,j:=d ji,j-aji+di,j;ji:=ji-1；/di ，0 永远为 1end;这不能叫作状态转移方程，但本人才疏学浅，无法写出这种状态的转移方程，还请大家见谅解释一下：a中存的是本题中提供的面值（从大到小） ，ji 表示可以去前 ji 个面值（想一想，为什么是从大到小） 。这样操作一遍后，本题的数组变为：i j 0 1 2 3 4 5 6 7 8 9 10动态规划算法及算法思路的分析 石家庄二中 贾志豪- 9 -（5） 1 0 0 0
13、 0 1 0 0 0 0 1（5，2） 1 0 1 0 1 1 1 1 1 1 2（5，2，1）1 1 2 2 3 4 5 6 7 8 10本题原程序见附录一。习题1、相邻项序列(GDOI97 第四题)问题描述： 对于一个 N*N(=100)的正整数矩阵 M，存在从 MA1，B1 开始到 MA2，B2结束的相邻项序列 .两个项 MI，J和 MK，L相邻的件是指满足如下情况之一：(1)I=K+-1 和 J=L (2)I=K 和 J=L+-1。 任务：从文件中输入矩阵 M，再读入 K(K=4)组 MA1，B1和MA2，B2的值。对于每一组 MA1，B1和 MA2，B2，求一相邻项序列，使得相邻项之
14、差的绝对值之和为最小。输入格式：4 N1 9 6 12 每行 N 个数据，共 N 行8 7 3 5 5 9 11 11动态规划算法及算法思路的分析 石家庄二中 贾志豪- 10 -7 3 2 62 K4 1 1 4 表示 A1,B1 和 A2,B2 的值，共 K 行 2 2 3 4 输出格式：1 17 第一组数据相邻项之差的绝对值之和的最小值是 177 5 8 7 9 6 12第一组数据的相邻项序列2 47 9 11 11 本题解析见附录二（本题解析摘自国家集训队论文）2. Perform 巡回演出 (GDKOI2000)题目描述:Flute 市的 Phlharmoniker 乐团 2000 年准备到 Harp 市做一次大型演出,本着普及古典音乐的目的,乐团指挥 L.Y.M 准备在到达 Harp 市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地 Harp 市(乐团可多次在同一城市演出 ).由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.输入:输入文件包括若干个场景.每个场景的描述由一对整数 n(2=n=10)
