资源描述：
《中华中学动态规划讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、中华中学动态规划讲义——周默介绍动态规划是NOIP中非常重要的一类题型。在动态规划中，算法是最难想到的，当你想到了算法，实现也就迎刃而解。今天，我们将强调算法的研究，不作上机实践递推递推是动态规划的根本，我们首先花一点时间进行递推训练递推关系是一种简洁高效的常见数学模型，比如我们熟悉的Fibonacci数列问题。在这种类型的问题中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有一定的关联，这种关联一般是通过一个“递推关系式”来表示的。求解问题时我们从初始的一个或若干个数据项出发，通过递推关系逐步推进，从而得到
2、最终结果，这种求解问题的方法叫“递推法”。其中，初始的若干数据项称为“边界”。解决递推问题有三个重点：一、如何建立正确的递推关系二、递推关系有何性质三、递推关系式如何求解递推按照我们推导问题的方向，常分为顺推法和倒推法。例1、有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。试求出蜜蜂从蜂房a爬到蜂房b的可能路线数。问题分析：这是一道很典型的Fibonacci数列类题目，其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行”的限制，决定了蜜蜂到b点的路径只能是从b-1点或b-2点到达的，故fn=fn
3、-1+fn-2(a+2<=n<=b)，边界条件fa=1，fa+1=1。例2、打印杨晖三角形的前10行。杨晖三角形的前5行如左下图所示。问题分析：我们观察左上图不太容易找到规律，但如果将左上图转化为右上图就不难发现杨辉三角形其实就是一个二维表（数组）的下三角部分。假设用二维数组yh存储，每行首尾元素都为1，且其中任意一个非首尾元素yh[i,j]的值其实就是yh[i-1,j-1]与yh[i-1,j]的和，另外每一行的元素个数刚好等于行数。有了这些规律，给数组元素赋值就不难了，而要打印杨晖三角形，只需控制一下每行输出的起始位置即
4、可。例3、猴子第1天摘下若干个桃子,当即吃了一半又一个。第2天又把剩下的桃吃了一半又一个,以后每天都吃前一天剩下的桃子的一半又一个,到第10天猴子想吃时,只剩下一个桃子。问猴子第1天一共摘了多少桃子?问题分析：已知条件第10天剩下1个桃子，隐含条件每一次前一天的桃子个数等于后一天桃子的个数加1的2倍。我们采取逆向思维的方法,从后往前推，可用倒推法求解。VarS,I:LongInt;BeginS:=1;{第10天只有一个桃子}ForI:=9DownTo1DoS:=(S+1)*2;{第10天依次求前一天的桃Writeln(S)
5、;子数}End.程序填空：设有一个n级的楼梯(1<=n<=12),编号从下到上依次为1至n,其中有若干级为坏的。有一个人上楼梯时一步可走1级、或2级、或3级(坏级只能跨过不能踏上,但级数照算)。问:这个人从楼下走到第n级,共有多少种不同的走法?例如:当n=l时(无坏级情况下),仅有1种走法n=2时(无坏级情况下),有:1级+l级或2级共2种走法n=3时(第二级为坏级情况下),有:1级+2级,直接3级,共2种走法【程序说明】用递推方法求解。用集合记录坏级。varx,i,n,fl,f2,f3,f4:longint;s:seto
6、f0..30;beginreadln(n);s:=①readln(x);{x:坏级,以0结束}while(x<>O)dobegins:=②readln(x);end;If(1ins)thenf1:=0elsefl:=1;If(2ins)thenf2:=0elsef2:=③If(3ins)thenf3:=0elsef3:=1+f1+f2;ifn=1thenf4:=f1elseifn=2thenf4:=f2elseifn=3thenf4:=f3elsebeginfori:=4tondobeginif(iins)thenf4:=
7、0elsef4:=④fl:=f2;f2:=f3;f3:=f4;end;end;writeln(f4);readln;end.例4、棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，A点(0,0)、B点(n,m)(n,m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。【样
8、例】knight.inknight.out66336分析：本题可用搜索算法，但N,M=15就会超时。再分析题意会发现：要到达棋盘上的一个点，只能从左边过来或是从上面过来。根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起点到
