动态规划经典教程.doc

动态规划经典教程.doc

《动态规划经典教程.doc》由会员分享，可在线阅读，更多相关《动态规划经典教程.doc（46页珍藏版）》请在冰点文库上搜索。

动态规划经典教程

引言：

本人在做过一些题目后对DP有些感想，就写了这个总结：

第一节动态规划基本概念

一，动态规划三要素：

阶段，状态，决策。

他们的概念到处都是，我就不多说了，我只说说我对他们的理解：

如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。

显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。

每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。

下面举个例子：

要生产一批雪糕，在这个过程中要分好多环节：

购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就去销售……，这样没个环节就可以看做是一个阶段；产品在不同的时候有不同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由液态变成固态=_=||）。

每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。

一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。

经过这个例子相信大家对动态规划有所了解了吧。

下面在说说我对动态规划的另外一个理解：

用图论知识理解动态规划：

把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向边，状态转移的代价就是边上的权。

这样就形成了一个有向无环图AOE网（为什么无环呢？

往下看）。

对这个图进行拓扑排序，删除一个边后同时出现入度为0的状态在同一阶段。

这样对图求最优路径就是动态规划问题的求解。

二，动态规划的适用范围

动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？

一般在题目中出现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件：

最优子结构（最优化原理）

无后效性

最优化原理在下面的最短路径问题中有详细的解答；

什么是无后效性呢？

就是说在状态i求解时用到状态j而状态j就解有用到状态k…..状态N。

而求状态N时有用到了状态i这样求解状态的过程形成了环就没法用动态规划解答了，这也是上面用图论理解动态规划中形成的图无环的原因。

也就是说当前状态是前面状态的完美总结，现在与过去无关。

。

。

当然，有是换一个划分状态或阶段的方法就满足无后效性了，这样的问题仍然可以用动态规划解。

三，动态规划解决问题的一般思路。

拿到多阶段决策最优化问题后，第一步要判断这个问题是否可以用动态规划解决，如果不能就要考虑搜索或贪心了。

当却定问题可以用动态规划后，就要用下面介绍的方法解决问题了：

（1）模型匹配法：

最先考虑的就是这个方法了。

挖掘问题的本质，如果发现问题是自己熟悉的某个基本的模型，就直接套用，但要小心其中的一些小的变动，现在考题办都是基本模型的变形套用时要小心条件，三思而后行。

这些基本模型在先面的分类中将一一介绍。

（2）三要素法

仔细分析问题尝试着确定动态规划的三要素，不同问题的却定方向不同：

先确定阶段的问题：

数塔问题，和走路问题（详见解题报告）

先确定状态的问题：

大多数都是先确定状态的。

先确定决策的问题：

背包问题。

（详见解题报告）

一般都是先从比较明显的地方入手，至于怎么知道哪个明显就是经验问题了，多做题就会发现。

（3）寻找规律法：

这个方法很简单，耐心推几组数据后，看他们的规律，总结规律间的共性，有点贪心的意思。

（4）边界条件法

找到问题的边界条件，然后考虑边界条件与它的领接状态之间的关系。

这个方法也很起效。

（5）放宽约束和增加约束

这个思想是在陈启锋的论文里看到的，具体内容就是给问题增加一些条件或删除一些条件使问题变的清晰。

第二节动态规划分类讨论

这里用状态维数对动态规划进行了分类：

1.状态是一维的

1．1下降/非降子序列问题：

问题描述：

 {挖掘题目的本质，一但抽象成这样的描述就可以用这个方法解}

在一个无序的序列a1,a2,a3,a4…an里，找到一个最长的序列满足：

ai<=aj<=ak…<=am,且iaj>ak…>am,且i>j>k…>m.（最长下降子序列）。

问题分析：

如果前i-1个数中用到ak（ak>ai或ak<=ai）构成了一个的最长的序列加上第I个数ai就是前i个数中用到i的最长的序列了。

那么求用到ak构成的最长的序列有要求前k-1个数中……

从上面的分析可以看出这样划分问题满足最优子结构，那满足无后效性么？

显然对于第i个数时只考虑前i-1个数,显然满足无后效性，可以用动态规划解。

分析到这里动态规划的三要素就不难得出了：

如果按照序列编号划分阶段，设计一个状态opt[i]表示前i个数中用到第i个数所构成的最优解。

那么决策就是在前i-1个状态中找到最大的opt[j]使得aj>ai（或aj<=ai），opt[j]+1就是opt[i]的值；用方程表示为：

{我习惯了这种写法，但不是状态转移方程的标准写法}

opt[i]=max（opt[j]）+1  （0<=j

opt[i]=max（opt[j]）+1  （0<=jai）       {最长下降子序列}

实现求解的部分代码：

opt[0]:

=maxsize；{maxsize为maxlongint或-maxlongint}

for i:

=1tondo

forj:

=0toi-1do

if（a[j]>a[i]）and（opt[j]+1>opt[i]）then

opt[i]:

=opt[j]+1;

ans:

=-maxlongint;

fori:

=1tondo

ifopt[i]>ansthenans:

=opt[i];               {ans为最终解}

复杂度：

从上面的实现不难看出时间复杂度为O（N2），空间复杂度O（N）；

例题1拦截导弹（missile.pas/c/cpp）来源：

NOIP1999（提高组）第一题

【问题描述】

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：

虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

【输入文件】missile.in

单独一行列出导弹依次飞来的高度。

【输出文件】missile.out

两行，分别是最多能拦截的导弹数，要拦截所有导弹最少要配备的系统数

【输入样例】

38920715530029917015865

【输出样例】

6

2

【问题分析】

有经验的选手不难看出这是一个求最长非升子序列问题，显然标准算法是动态规划。

以导弹依次飞来的顺序为阶段，设计状态opt[i]表示前i个导弹中拦截了导弹i可以拦截最多能拦截到的导弹的个数。

状态转移方程：

opt[i]=max（opt[j]）+1 （h[i]>=h[j],0=

最大的opt[i]就是最终的解。

这只解决了第一问，对于第二问最直观的方法就是求完一次opt[i]后把刚才要打的导弹去掉，在求一次opt[i]直到打完所有的导弹，但这样做就错了。

不难举出反例：

61732

错解：

632/1/7  正解：

61/732

其实认真分析一下题就回发现：

每一个导弹最终的结果都是要被打的，如果它后面有一个比它高的导弹，那打它的这个装置无论如何也不能打那个导弹了，经过这么一分析，这个问题便抽象成在已知序列里找最长上升序列的问题。

求最长上升序列和上面说的求最长非升序列是一样的，这里就不多说了。

复杂度：

时间复杂度为O（N2），空间复杂度为O（N）。

【源代码】

programmissile;

const

fin='missile.in';

fout='missile.out';

maxn=10000;

var

a,opt:

array[0..maxn]oflongint;

n,anslen,anstime:

longint;

procedure init;

var

x:

longint;

begin

assign（input,fin）;

reset（input）;

assign（output,fout）;

rewrite（output）;

n:

=0;

repeat

inc（n）;

read（a[n]）;

untilseekeof;

end;

proceduremain;

var

i,j:

longint;

begin

fillchar（opt,sizeof（opt）,0）;

a[0]:

=maxlongint;

fori:

=1tondo

forj:

=i-1downto0do

if（a[j]>=a[i]）and（opt[j]+1>opt[i]）then

opt[i]:

=opt[j]+1;

anslen:

=0;

fori:

=1tondo

ifopt[i]>anslenthen

anslen:

=opt[i];

fillchar（opt,sizeof（opt）,0）;

a[0]:

=-maxlongint;

fori:

=1tondo

forj:

=i-1downto0do

if（a[j]opt[i]）then

opt[i]:

=opt[j]+1;

anstime:

=0;

fori:

=1tondo

ifopt[i]>anstimethen

anstime:

=opt[i];

end;

procedureprint;

begin

writeln（anslen）;

writeln（anstime）;

close（input）;

close（output）;

end;

begin

init;

main;

print;

end.

例题二合唱队形（chorus.pas/c/cpp）来源：

NOIP2004（提高组）第一题

N位同学站成一排，音乐老师要请其中的（N-K）位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：

设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，  则他们的身高满足T1<...Ti+1>…>TK（1<=i<=K）。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入文件】

输入文件chorus.in的第一行是一个整数N（2<=N<=100），表示同学的总数。

第一行有n个整数，用空格分隔，第i个整数Ti（130<=Ti<=230）是第i位同学的身高（厘米）。

【输出文件】

输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

【样例输入】

8

186186150200160130197220

【样例输出】

4

【数据规模】

对于50％的数据，保证有n<=20；

对于全部的数据，保证有n<=100。

【问题分析】

出列人数最少，也就是说留的人最多，也就是序列最长。

这样分析就是典型的最长下降子序列问题。

只要枚举每一个人站中间时可以的到的最优解。

显然它就等于，包括他在内向左求最长上升子序列，向右求最长下降子序列。

我们看一下复杂度：

计算最长下降子序列的复杂度是O（N2），一共求N次，总复杂度是O（N3）。

这样的复杂度对于这个题的数据范围来说是可以AC的。

但有没有更好的方法呢？

其实最长子序列只要一次就可以了。

因为最长下降（上升）子序列不受中间人的影响。

只要用OPT1求一次最长上升子序列，OPT2求一次最长下降子序列。

这样答案就是N-max（opt1[i]+opt2[i]-1）.

复杂度由O（N3）降到了O（N2）。

【源代码】

programchorus;

const

fin='chorus.in';

fout='chorus.out';

maxn=200;

var

opt1,opt2,a:

array[0..maxn]oflongint;

n,ans:

longint;

procedureinit;

var

i:

longint;

begin

assign（input,fin）;

reset（input）;

assign（output,fout）;

rewrite（output）;

readln（n）;

fori:

=1tondo

read（a[i]）;

end;

proceduremain;

var

i,j:

longint;

begin

a[0]:

=-maxlongint;

fori:

=1tondo

forj:

=i-1downto0do

if（a[j]opt1[i]）then

opt1[i]:

=opt1[j]+1;

a[n+1]:

=-maxlongint;

fori:

=ndownto1do

forj:

=i+1ton+1do

if（a[j]opt2[i]）then

opt2[i]:

=opt2[j]+1;

ans:

=0;

fori:

=1tondo

ifopt1[i]+opt2[i]>ansthen

ans:

=opt1[i]+opt2[i];

end;

procedureprint;

begin

writeln（n-ans+1）;

close（input）;

close（output）;

end;

begin

init;

main;

print;

end.

例题3BuyLowBuyLower（buylow.pas/c/cpp）来源:

USACO4-3-1

【问题描述】

“逢低吸纳”是炒股的一条成功秘诀。

如果你想成为一个成功的投资者，就要遵守这条秘诀:

"逢低吸纳,越低越买"

这句话的意思是：

每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。

给定连续的N天中每天的股价。

你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。

写一个程序，求出最多能买几次股票。

以下面这个表为例,某几天的股价是:

天数1 2 3 4 5 6 7 8 9 101112

股价686954646864706778629887

这个例子中,聪明的投资者（按上面的定义），如果每次买股票时的股价都比上一次买时低，那么他最多能买4次股票。

一种买法如下（可能有其他的买法）:

天数2 5 6 10

股价69686462

【输入文件】buylow.in

第1行:

N（1<=N<=5000）,表示能买股票的天数。

第2行以下:

N个正整数（可能分多行），第i个正整数表示第i天的股价.这些正整数大小不会超过longint（pascal）/long（c++）.

【输出文件】buylow.out

只有一行，输出两个整数：

能够买进股票的天数长度达到这个值的股票购买方案数量

在计算解的数量的时候，如果两个解所组成的字符串相同，那么这样的两个解被认为是相同的（只能算做一个解）。

因此，两个不同的购买方案可能产生同一个字符串，这样只能计算一次。

【输入样例】

12

6869546468647067

78629887

【输出样例】

42

【问题分析】

从题目描述就可以看出这是最长下降子序列问题，于是求解第一问不是难事，以天数为阶段，设计状态opt[i]表示前i天中要买第i天的股票所能得到的最大购买次数。

状态转移方程：

opt[i]=max（opt[j]）+1 （a[i]>=a[j],0=

最大的opt[i]就是最终的解。

第二问呢，稍麻烦一点。

从问题的边界出发考虑问题，当第一问求得一个最优解opt[i]=X时，

在1到N中如果还有另外一个opt[j]=x那么选取J的这个方案肯定是成立的。

是不是统计所有的opt[j]=x的个数就是解了呢？

显然没那么简单，因为选取Ｊ这天的股票构成的方案不见得＝１，看下面一个例子：

５　6 4　3　１2

方案一：

５４３１

方案二：

５４３２

方案三：

６４３１

方案四：

６４３２

x=4

也就是所虽然opt[5]=X和opt[6]=X但个数只有两个，而实际上应该有四个方案，但在仔细观察发现，构成opt[5]=x的这个方案中opt[j]=x-1的方案数有两个,opt[j]=x-2的有一个，opt[j]=x-3的有一个……

显然这是满足低归定义的设计函数F（i）表示前I张中用到第i张股票的方案数。

递推式：

1 （i=0）

F（i）=

Sum（F（j）） （0<=j<=n,a[j]>a[i],opt[j]=opt[i]-1） {sum代表求和}

答案=sum（F（j））   {0

复杂度：

求解第一问时间复杂度是O（N2）,求解第二问如果用递推或递归+记忆化时间复杂度仍为O（N2）但要是用赤裸裸的递归那就复杂多了……，因为那样造成了好多不必要的计算。

你认为这样做就解决了这道题目了么？

还没有，还要注意一些东西：

（1）如果有两个方案中出现序列一样，视为一个方案，要需要加一个数组next用next[i]记录和第i个数情况一样（即：

opt[i]=opt[j]且a[i]=a[j]）可看做一个方案的最近的位置。

递推时j只要走到next[i]即可。

（2）为了方便操作可以将a[n+1]赋值为-maxlongint这样可以认为第n+1个一定可以买，答案就是sum（F（n+1））。

（3）看数据规模显然要用高精度。

注：

USACO上最后一个点错了。

我在程序中做了处理。

【源代码】

programbuylow;

const

fin='buylow.in';

fout='buylow.out';

maxn=5010;

maxsize=10;

jz=100000000;

type

arrtype=array[0..maxsize]oflongint;

var

a,opt,next:

array[0..maxn]oflongint;

F:

array[0..maxn]ofarrtype;

n:

longint;

procedureinit;

var

i:

longint;

begin

assign（input,fin）;

reset（input）;

assign（output,fout）;

rewrite（output）;

readln（n）;

ifn=5then               {最后一个点错了，我只好这么写了}

begin

writeln（'25'）;

close（input）;

close（output）;

halt;

end;

fori:

=1tondo

read（a[i]）;

end;

procedureHinc（varx:

arrtype;y:

arrtype）;

var

i,z:

longint;

begin

z:

=0;

fori:

=1tomaxsizedo

begin

z:

=zdivjz+x[i]+y[i];

x[i]:

=zmodjz;

end;

end;

proceduremain;

var

i,j:

longint;

begin

a[0]:

=maxlongint;

a[n+1]:

=-maxlongint;

fori:

=1ton+1do

forj:

=0toi-1do

if（a[j]>a[i]）and（opt[j]+1>opt[i]） then

opt[i]:

=opt[j]+1;

fori:

=1tondo

begin

j:

=i-1;

while（j>0）and（（opt[i]<>opt[j]）or（a[i]<>a[j]））do

dec（j）;

next[i]:

=j;

end;

F[0,1]:

=1;

fori:

=1ton+1do

forj:

=i-1downtonext[i]do

if（opt[j]=opt[i]-1）and（a[j]>a[i]）then

Hinc（F[i],F[j]）;

end;

procedureprint;

var

i,top,m:

longint;

begin

write（opt[n+1]-1,''）;

top:

=maxsize;

while（top>1）and（F[n+1][top]=0）do

dec（top）;

write（F[n+1,top]）;

fori:

=top-1downto1do

begin

m:

=F[n+1,i];

whilem

begin

write（'0'）;

m:

=m*10;

end;

write（F[n+1,i]）;

end;

writeln;

close（input）;

close（output）;

end;

begin

init;

main;

print;

end.

例题4船（ships.pas/c/cpp）来源：

《奥赛经典》（提高篇）

【问题描述】

PALMIA国家被一条河流分成南北两岸，南北两岸上各有N个村庄。

北岸的每一个村庄有一个唯一的朋友在南岸，且他们的朋友村庄彼此不同。

每一对朋友村庄想要一条船来连接他们，他们向政府提出申请以获得批准。

由于河面上常常有雾，政府决定禁止船只航线相交（如果相交，则很可能导致碰船）。

你的任务是编写一个程序，帮助政府官员决定批准哪些船只航线，使得不相交的航线数目最大。

【输入文件】ships.in

输入文件由几组数据组成。

每组数据的第一行有2个整数X，Y，中间有一个空格隔开，X代表PALMIA河的长度（10<=X<=6000），Y代表河的宽度（10<=Y<=100）。

第二行包含整数N，表示分别坐落在南北两岸上的村庄的数目（1<=N<=5000）。

在接下来的N行中，每一行有两个非负整数C，D，由一个空格隔开，分别表示这一对朋友村庄沿河岸与PALMIA河最西边界的距离（C代表北岸的村庄，D代表南岸的村庄），不存在同岸又同位置的村庄。

最后一组数据的下面仅有一行，是两个0，也被一空格隔开。

【输出文件】ships.out

对输入文件的每一组数据，输出文件应在连续的行中表示出最大可能满足上述条件的航线的数目。

【输入样例】

304

7

224

26

103

1512

98

1717

42

00

【