《动态规划习题精讲》由会员分享，可在线阅读，更多相关《动态规划习题精讲（62页珍藏版）》请在金锄头文库上搜索。
1、如果您需要使用本文档，请点击下载按钮下载!信息学竞赛中的动态规划专题哈尔滨工业大学 周谷越【关键字】动态规划 动机 状态 典型题目 辅助方法 优化方法【摘要】本文针对信息学竞赛（面向中学生的Noi以及面向大学生的ACM/ICPC）中的动态规划算法，从动机入手，讨论了动态规划的基本思想和常见应用方法。通过一些常见的经典题目来归纳动态规划的一般作法并从理论上加以分析和说明。并介绍了一些解决动态规划问题时的一些辅助技巧和优化方法。纵观全文可知，动态规划的关键在于把握本质思想的基础上灵活运用。【目录】1.动态规划的动机和基本思想1.1.解决重复子问题1.2.解决复杂贪心问题2.动态规划状态的划分方法2
2、.1.一维状态划分2.2.二维状态划分2.3.树型状态划分3.动态规划的辅助与优化方法3.1.常见辅助方法3.2.常见优化方法4.近年来Noi动态规划题目分析4.1 Noi2005瑰丽华尔兹4.2 Noi2005聪聪与可可4.3 Noi2006网络收费4.4 Noi2006千年虫附录 参考书籍与相关材料0 / 66第0页/共50页如果您需要使用本文档，请点击下载按钮下载!1.动态规划的动机和基本思想首先声明，这里所说的动态规划的动机是从竞赛角度出发的动机。1.1 解决重复子问题对于很多问题，我们利用分治的思想，可以把大问题分解成若干小问题，然后再把各个小问题的答案组合起来，得到大问题的解答。这
3、类问题的共同点是小问题和大问题的本质相同。很多分治法可以解决的问题（如quick_sort，hanoi_tower等）都是把大问题化成2个以内的不相重复的小问题，解决的问题数量即为(log2n / k)。而考虑下面这个问题：USACO 1.4.3 Number Triangleshttp:/122.139.62.222/problem.php?id=1417【题目描述】考虑在下面被显示的数字金字塔。写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。73 88 1 02 7 4 44 5 2 6 1在上面的样例中，从7到3到8到7
4、到5的路径产生了最大和：30。【输入格式】第一个行包含 R(1= R FI-1,J-1 ThenFI,J = FI-1,J + AI,JElseFI,J = FI-1,J-1 + AI,J接下来我们从理论上来讨论使用动态规划的条件。对于一种状态划分的方法来说，状态只与状态本身的性质有关，而与如何达到该状态等其他条件一概无关的性质叫做无后效性。由于存在无后效性，决策只能从决策本身的性质来确定，使得某一阶段的状态只与它所在阶段的前一阶段的状态有关。可以看出，存在无后效性是应用动态规划的前提条件。而考虑动态规划的正确性时，问题则需要满足最优子结构。所谓最优子结构，即当前一阶段的状态最优时，通过状态转
5、移方程得到的状态也能达到最优。理论上看，无后效性和最优子结构是使用动态规划时的两个基本条件，而具体应用动态规划时更多凭借的是经验。下面再引出一道经典题目做一下分析：2 / 66第2页/共50页如果您需要使用本文档，请点击下载按钮下载!ACM/ICPC Shanghai2001 Skiinghttp:/122.139.62.222/problem.php?id=1862【题目描述】滑雪是一项很受欢迎的体育运动，为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡。我们想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：1 2 3
6、4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9我们可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-.-3-2-1更长。事实上，这是最长的一条。【输入格式】输入的第一行表示区域的行数R和列数C(1 = R,C = 500)。下面是R行，每行有C个整数，代表高度h，0=h 0 ThenReturn ArrI,JInt P, Ans = 0For P = 1 to 4 DoIf (I+DXP,J+DYP) In Map) And (HI+DXP,J+
7、DYP HI,J) ThenIf (Ans FI+DXP,J+DYP)Ans = FI+DXP,J+DYPArrI,J = Ans + 1Return ArrI,J同样是动态规划，是什么使得两道题目代码的主干部分相差巨大呢？这里讨论一下动态规划的两种实现形式递推和记忆化搜索。首先，可以说所有用递推实现的动态规划均可以利用记忆化搜索实现。而某些题目之所以可以用递推求解，是因为这类题目同一阶段的状态表示上有很大的相关性，比如数字矩阵中某一行或列，这使得我们可以计算一个阶段的所有状态后再计算下一状态。而某些题目中利用动态规划划分的同一阶段的状态表示上没有多大相关性，比如Skiing里面的状态，从某点
8、做起点每滑动一步为一个阶段，我们无法用一个准确的可以直接利用的集合将一个阶段中的状态表示出来，只能从已知状态去找和它相关联的状态。对于Skiing我们已知的是目标状态（即四面都不比该点高的点），通过边界条件（即四面都比该点高的最优值为1），便可以进行记忆化搜索。利用递推实现动态规划时，单位操作时间小，可以方便地使用一些优化；而利用记忆化搜索实现动态规划时，单位操作时间大，但可以避免计算一些不必要的状态。总地来说，相比于用状态空间搜索的方法解决这类存在重复子问题的题目，使用动态规划增大了空间的开销，但提高了时间效率。1.2 解决复杂贪心问题接下来，进入下一话题。我们考虑一下我们熟知的贪心算法和动
9、态规划的关系，我看过很多写贪心算法和动态规划之间区别的材料，在这里我们不谈这个，而是要讨论动态规划与贪心算法之间的联系。如果我们把每一步贪心作为一个阶段，那么可以认为每个阶段只有一个状态，再把贪心策略看作状态转移方程，那么这样是否也是一种“动态规划”呢？实际上，它们二者之间的差别就在数据的维护上，有很多贪心问题在采取一次贪心策略之后要对数据进行全盘的维护，而我们讲的动态规划一般没有这个步骤。而这个维护的目的是什么呢？是为了保证正确性，和动态规划中的最优子结构的目的一样，那么就说明目前的状态划分不具有最优子结构，那么我们是否能够通过改变状态的划分方法来代替这个维护并使新划分的状态具有最优子结构呢
10、？这里直接给出结论：对于某些分步讨论的贪心决策问题，我们可以通过扩展状态使之能够用动态规划解决。扩展出的状态的作用就是为了保证正确性，也就是保证最优子结构。举一个简单的例子：给出N个数，要从其中取M个求和，并使和尽量大。这明显是一个贪心可解的问题，把数字从大到小排序后取前M个求和即可。那么我们同样也可以扩展出一部分状态。我们设FI,J表示前I个数字中取了J个数字得到的最大和，则有：FI,J = Max (FI1,J,FI-1J-1 + AJ)。那些贪心算法并不用考虑的“多余”状态就是扩展出的状态，举个实例来说明：N = 5 , M = 3时，A = 1, 2, 3, 4, 5。那么显然1和2都不会被取到，但数组F中的F1,1, F2,1 和F2,2都是由1和2组成的状态，从贪心的角度看，它们就是多余的，就是为了使用动态规划扩展出来的状态。当然，就这道题目来看，贪心算法无论是从思维角
