搜索
动态规划参与竞赛的同学应由竞争关系和独立关系（你做你的，我干我的，程序和算法互相保密，彼此津津乐道于对方的失败和自己的成功）转向合作学习的关系（通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务）2F(n)=1ifn=0or1F(n-1)+F(n-2)ifn1n012345678910F(n)1123581321345589斐波纳契数列F(n)3递归vs动态规划递归版本:F(n)1ifn=0orn=1then2return13else4returnF(n-1)+F(n-2)动态规划:F(n)1A[0]=A[1]←12fori←2tondo3A[i]←A[i-1]+A[i-2]4returnA[n]太慢!有效率!算法复杂度是O(n)4方法概要构造一个公式，它表示一个问题的解是与它的子问题的解相关的公式.E.g.F(n)=F(n-1)+F(n-2).为这些子问题做索引，以便它们能够在表中更好的存储与检索(i.e.,数组array【】)以自底向上的方法来填写这表格;首先填写最小子问题的解.这就保证了当我们解决一个特殊的子问题时,可以利用比它更小的所有可利用的子问题的解.由于历史原因,我们称这种方法为：动态规划.在上世纪40年代末(计算机普及很少时),这些规划设计是与”列表“方法相关的.5动态规划算法算法思想将待求解的问题分解成若干个子问题，并存储子问题的解而避免计算重复的子问题，并由子问题的解得到原问题的解。动态规划算法通常用于求解具有某种最优性质的问题。动态规划算法的基本要素：最优子结构性质和重叠子问题。6最优子结构性质：问题的最优解包含着它的子问题的最优解。即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些问题被反复计算多次。对每个子问题只解一次，然后将其解保存起来，以后再遇到同样的问题时就可以直接引用，不必重新求解。7动态规划解决问题的基本特征1.动态规划一般解决最值（最优，最大，最小，最长……）问题；2.动态规划解决的问题一般是离散的，可以分解（划分阶段）的；3.动态规划解决的问题必须包含最优子结构，即可以由（n－1）的最优推导出n的最优8动态规划算法的4个步骤：1.刻画最优解的结构特性.（一维，二维，三维数组）2.递归的定义最优解.（状态转移方程）3.以自底向上的方法来计算最优解.4.从计算得到的解来构造一个最优解.解决问题的基本步骤9例题一.斐波纳契数列F(n)F(n)=1ifn=0or1F(n-1)+F(n-2)ifn1步骤1：用F（n）表示在斐波纳契数列中第n个数的值；步骤2：状态转移方程：步骤3：以自底向上的方法来计算最优解n012345678910F(n)1123581321345589步骤4：在数组中分析构造出问题的解；10例题二.输入n，求出n！F(n)=1ifn=0or1F(n-1)*nifn1步骤1：用F（n）表示n！的值；步骤2：状态转移方程：步骤3：以自底向上的方法来计算最优解n012345678910F(n)11262412072011例题三：排队买票问题一场演唱会即将举行。现有n个歌迷排队买票，一个人买一张，而售票处规定，一个人每次最多只能买两张票。假设第i位歌迷买一张票需要时间Ti（1≤i≤n），队伍中相邻的两位歌迷（第j个人和第j+1个人）也可以由其中一个人买两张票，而另一位就可以不用排队了，则这两位歌迷买两张票的时间变为Rj，假如RjTj+Tj+1，这样做就可以缩短后面歌迷等待的时间，加快整个售票的进程。现给出n,Tj和Rj，求使每个人都买到票的最短时间和方法。12分析：如果前i个人买票的最优买票方式一确定，比如第i-1个人买一张票，则前i-1个人的买票方式也一定是最优的。即问题的最优解包含子问题的最优解。12345i…in-1nn-2…步骤1：用F（i）表示前i个人买票的最优方式，即所需最短时间；现在要决定F(i)需要考虑两种情况：（1）第i个人的票自己买（2）第i个人的票由第i-1个人买步骤2：状态转移方程：min步骤3：以自底向上的方法来计算最优解1100[]1min{[1],[2]}iiifiTifiTfiR-ì=ïïïï==íïï-+-+ïïî13程序的实现BuyTicks(T,R)1n←length[T]2f[0]←03f[1]←T[1]4fori←2tondo5f[i]←f[i-2]+R[i-1]6iff[i]f[i-1]+T[i]then7f[i]←f[i-1]+T[i]8returnf14例题四：求最长不降子序列1．问题描述设有一个正整数的序列：b1,b2,…，bn，对于下标i1i2…＜im，若有bi1≤bi2≤…≤bim则称存在一个长度为m的不下降序列。例如，下列数列13791638243718441921226315对于下标i1=1，i2=4，i3=5，i4=9，i5=13，满足13＜16＜38＜44＜63,则存在长度为5的不下降序列。但是，我们看到还存在其他的不下降序列:i1=2，i2=3，i3=4，i4=8，i5＝10，i6=11，i7=12，i8=13，满足：7＜9＜16＜18＜19＜21＜22＜63，则存在长度为8的不下降序列。问题为：当b1,b2,…，bn给出之后，求出最长的不下降序列。步骤1：用F（i）表示第i项到最后一项最长不下降序列的长度的值；步骤2：状态转移方程；d[i]表示数列中第i项的值；步骤3：以自底向上的方法来计算最优解[]1max{[],}1[][]FiiNFjijndidjìïïïï==íïï=+ïïî15拓展1：拦截导弹（vijos1303）某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。样例：INPUTOUTPUT389207155300299170158656（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）16拓展2：低价购买“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(216范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算最大购买次数。这里是某支股票的价格清单：日期123456789101112价格686954646864706778629887最优秀的投资者可以购买最多4次股票，可行方案中的一种是：日期25610价格69686462输入第1行:N(1=N=5000)，股票发行天数第2行:N个数，是每天的股票价格。输出输出文件仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(=231)当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这2种方案被认为是相同的。17拓展3：合唱队形（vijis1098）N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1...TiTi+1…TK(1=i=K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。输入的第一行是一个整数N(2=N=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130=Ti=230)是第i位同学的身高(厘米)。输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。样例输入8186186150200160130197220样例输出：418例题五.马拦过河卒[问题描述]:如图，A点有一个过河卒，需要走到目标B点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图C点上的马可以控制9个点（图中的P1，P2…P8和C）。卒不能通过对方马的控制点。棋盘用坐标表示，A点（0，0）、B点（n,m）(n,m为不超过20的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定:CA，同时CB）。现在要求你计算出卒从A点能够到达B点的路径的条数。[输入]:键盘输入B点的坐标（n,m）以及对方马的坐标（X,Y）{不用盘错}[输出]:屏幕输出一个整数（路径的条数）。[输入输出样例]:输入：6632输出：1719步骤1：用F（X,Y）表示到棋盘上每个阶段(X,Y)的路径条数；步骤2：状态转移方程：步骤3：以自底向上的方法来计算最优解分析：阶段：棋盘上的每个可走的点；每个阶段的求解；F（X,Y）=F(X-1,Y)+F(X,Y-1)其中，F（0,0)=1F(0,Y)=1F(X,0)=120例题六：数字三角形问题1．问题描述设有一个三角形的数塔，顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，可以向左走，也可以向右走。如图10一1所示。问题：当三角形数塔给出之后，找出一条从第一层到达底层的路径，使路径的值最大。若这样的路径存在多条，任意给出一条即可。21步骤1二维数组D(X,y)描述问题，D(X,y)表示从顶层到达第X层第y个位置的最小路径得分。步骤2：状态转移方程阶段分析：D(1,1)=13到第x层的第y个位置有两种可能，要么走右分支得到，要么走左分支得到。D(X,y)＝min{D(X-1,y)，D(X-1,y-1}+a(X,y)D(1,1)＝a(1,1)22拓展：栈（vijos1122）【问题背景】栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n（图示为1到3的情况），栈A的深度大于n。现在可以进行两种操作，1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）2.将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）23使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由123生成序列231的过程。（原始状态如上图所示）12312313222323124你的程序将对给定的n，计算并输出由操作数序列1，2，…，n经过操作可能得到的输出序列的总数。【输入格式】输入文件只含一个整数n（1≤n≤18）【输出格式】输出文件只有一行，即可能输出序列的总数目【输入样例】3【输出样例】525例题七：最长公共子序列一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列:公共子序列中长度最长的子序列。最长公共子序列问题给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的一个最长公共子序列。例如:X=(A,B,C,B,D,A,B)X的子序列:所有X的子集(集合中元素按原来在X中的顺序排列)(A,B,D),(B,C,D,B),等等.26例子X=(A,B,C,B,D,A,B)X=(A,B,C,B,D,A,B)Y=(B,D,C,A,B,A)Y=(B,D,C,A