注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

xiaochen7777的博客

http://player.youku.com/player.php/sid/X

 
 
 

日志

 
 
关于我

了如指掌,方能规划人生。是说人应该了解一下自己手上的掌纹,它能对你的人生进行导航。(Q号:1583223327),共同学习。

网易考拉推荐
 
 

动态规划总结 (2009-03-06 20:54:15)  

2014-09-02 10:37:09|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
标签: 

杂谈

1.为什么要用动态规划?

众所周知,大多数题目都能用深搜或广搜解决,那为什么还要用动态规划呢?其原因就是在深搜或广搜中,大量状态都被重复运算,浪费了大量时间。而动态规划与深搜和广搜一个最大的不同就是动态规划在完成该状态的运算后将该状态的值记下来,以便以后使用,从而大大减少了运算量,提高程序在规定时间内解题能力。因为在分区联赛中对时间复杂度要求比较严格(大多数题都要求1s出解)而对空间复杂度要求不是十分严格(规定64m内存,而一般需要的内存不超过20m)。所以,对于一个解决分区联赛的程序来说,应适当地牺牲空间而追求时间,动态规划这一类算法很好地符合了这一点。所以对于大多数分区联赛题目,动态规划就是最好的,最能抓分的算法。

 

2.拿到一个题目,如何判断出他是动态规划类题目?

动态规划类题目有两个显著特点:具有最优子结构和后效性。对于最优子结构,由于动态规划类问题都是需要求极值,倘若不具有最优子结构,则无法求出所需的最值。对于无后效性,简单一点说就是当你处理完第i个状态,处理第i+1个状态时,就是天塌下来,第i个状态的值都不会改变了,要是在处理后面的状态时还要对前面的状态的值进行修改,就不是动态规划,而是搜索了。当符合了这两个特点时,你应该就能用动态规划方法做题了。

但是如果状态过多,在有限的内存下无法保存的话,还是要考虑其他方法(如“生日蛋糕”问题)。

 

3.对于一个动态规划题目,如何去思考它?

拿到一个动态规划题目,首先应该想到:它有哪几种状态需要我们保存,以便于在程序后期执行时加利利用,在分区联赛中,尽量把所有状态都列举记录下来,因为如前面所说,分区联赛对于空间复杂度的要求并不是十分严格,不必刻意地去减少状态数而降低空间复杂度,这样的话会增加编程的复杂度和编程的时间,对于你整场考试会有一定不利的影响。得分才是硬道理吗,程序能过,能得分就行,何必为了那几k内存的优化而久久放不下手呢?不过对于某些状态过多的动态规划题目,某些不必要的状态不必记录,否则就会出现数组清零占用大量时间,甚至超出内存等影响你得分的问题,这些都是不应该的,我们应该尽量避免出现这个问题。只记录有用的数据,丢弃无用的数据。

确定了需要保存的状态后,接下来很重要的一步就是确定每一步的决策,如前面所说,动态规划是具有最优子结构而且无后效性,也就是说程序在处理数据时就像在下棋一样需要一个决策去决定他该如何做,如何去利用已有的状态,这时决策的重要性就体现出来的。对于一个动态规划类试题,可能的状态可能不止一种,但正确的决策只有一种,可见制定决策对于解决动态规划类问题的重要性。

将决策制定好后应该就能很容易地写出状态转移方程(我一般不写),写状态转移方程有几个好处:可以将比较模糊的对于决策的描述变清晰,可以检查该决策和该状态配对时可行性,同时便于程序的编写。

一道动态规划试题的思考过程大致就是以上几步,接下来就该开始编写程序了

 

4.在编写动态规划程序时应注意些什么

在动态规划类程序的编写过程中,for循环嵌套是十分常见的,这样一来对于for循环语句和记录状态的数组就有比较严格的要求。对于for循环语句,一定要小心仔细,要是犯了把for i:=o to n do打成for i:=1 to n do或把for i:=n downto n do 打成了for i:=0 to n do等等一些问题的话,你哭都来不及,你明明想对了,可是编错了,没拿到分,怪谁呢?还有就是记录状态的数组稍微开大一点,对于纸上数据或是自己出的数据,有时检查不到数据结构的局限性要是有数据要调用f[0]而你只开了f:array[1..maxn] of dadatype呢?这不是程序的问题,而你没拿到分,是不是很冤?前面都说了分区联赛对于空间复杂度要求不大,多开一点就会要你命?还有一个一个重要的细节就是赋初值,一般来说初值都是1,但是对于一些题目,初值并不是1,不能没经过认真思考,想当然就把初值赋成1,这样做极易失分,一定要小心。最后还要注意输出的数据,一定要结合题目的规定和自己所编的程序来输出,不要盲目输出f[n]f[1,n]

还有就是个人习惯问题,如千万不能用“fillword”(参见cu牛的oi之路),编程时要缩进,两个子程序之间空一行……

 

 

 

动态规划类问题的几个典型例题

1.背包问题

背包问题可以说是动态规划大家族中最让人熟知的问题了,虽然很多人不是由他开始动态规划的路程(比如我,就是做数字三角形开始的)。但是背包问题绝对是动态规划所占比例最重的:0-1背包、有限k背包、无限k背包(USACO 2.3.4  Money System)、背包+并查集(VIJOS 1250“最勇敢的机器人”)、“树形”背包(noip2006金明的预算方案)……

所有背包问题的鼻祖都是0-1背包。其状态转移方程也最简单:f[I,j]:=f[i-1,j] or f[i-1,j-a[k]],一般可简化为f[i]:=f[i] or f[i-a[j]];

这类问题的总体思想也很简单,以重量i为状态,则f[i]的值是f[i]f[i-k]比较而得的。

 

2.递推类动态规划问题。

由于动态规划的无后效性,使得很多问题的最终状态都是由前面的若干个状态比较而得,如strling数,ural1031,ural073等,都是典型的递推类动态规划试题。

这一类动态规划试题的总体思想是从靠前的状态开始,逐步向后运算,后面的状态运算往往都要用到前面已有的状态,运算完毕后,按要求输出解。

 

3.博弈类动态规划试题。

这类动态规划试题的一个显著特点就是决策比较明确:在一个线性表中,每次取第i个或第j个,将f[I,i]设为初值,f[I,j]的值与f[i+1,j],f[I,j-1]有关。典型例题有usaco 3.2.4 game1.

 

4.树形动态规划

这类动态规划与一般的线性动态规划不同,他的数据结构是线性的,从而具有一个线性动态规划所没有的特点:在制定决策时需要同时考虑根、左子树和右子树,而且在记录状态时有时可能会涉及树的记录。

这类试题的代表有noip2003加分二叉树、ural1018苹果二叉树。

  评论这张
 
阅读(65)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017