DP-动态规划(动归)

动态规划动态规划什么是动态规划动态规划的条件动态规划的关键几种常见动态规划的种类例题分析什么是动态规划动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。由此不难得出结论：动态规划实质就是下面这个数塔的例子将形象地向我们展示这样的结论给你一个数字三角形,形式如下:1238518142110找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.当然，大家都很清楚的知道转移方程为opt[i,j]=max{opt[i-1,j],opt[i-1,j-1]}+a[i,j]，边界条件特殊处理即可。但只要仔细想想就会发现，这不过是一个加了强力减枝的记忆划搜索而已，因为每个点我们只记录到当前节点的最优解，因此省去了大量的重复计数和明显不是最优解的情况，从而使运行速度有了极大的优化动态规划的条件而在求解的过程中一道能使用动规解决的题必须具备以下几个条件无后效性,即某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。满足最优子结构性质，即一个问题的最优解必须是在子问题取得最优解的情况下决策出来的动态规划的过程可以简单地描述为找出最优解的性质，并刻画其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。动态规划的关键有明确的状态状态转移方程清晰正确线性动规背包问题区间动规树形动规下面让我们通过几个例子来了解这些基本动规的思考方法拦截导弹（Noip2002）某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹。状态的确定状态的表示——f[i]，表示当第i个导弹必须拦截时，前i个导弹中最多能拦截多少。每个导弹有一定的高度，当前状态就是以第i个导弹为最后一个拦截的导弹。以前状态就是在这个导弹之前拦截的那个导弹。对于f[i]，我们考察在i之前位置的导弹，找到所有可以连接上的导弹k（即满足其高度大于等于第i个导弹），选择其中f[k]值最大的一个，f[i]=f[k]+1；如果没有满足条件的k，则f[i]=1。这是线性动态规划的经典例题。代码Fori:=1tondoread(a[i]);Fori:=1tondof[i]:=1;Fori:=2tondoforj:=1toi-1doif(a[j]=a[i])and(f[j]+1f[i])thenf[i]:=f[j]+1;Ans:=0;Fori:=1tondoiff[i]ansthenans:=f[i];Writeln(ans);书的复制现在要把maxn本有顺序的书分给n个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。输入第一行两个整数maxn,n；（n=maxn=100）第二行maxn个整数，第i个整数表示第i本书的页数。输出共n行，每行两个正整数，第i行表示第i个人抄写的书的起始编号和终止编号。n行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。分析这个问题的关键在于划分好书的分配方式。由于一个人抄的书必须是连续的，因此不难发现这个问题是符合动态规划的条件的（即无后效性和最有子结构）。状态的确定我们用opt[i,j]表示前i个人抄到第j本书所需要消耗的最小时间。则opt[i,j]=min{max(opt[i-1,k],value[k+1..j])(i-1≤k≤j-1);最后输出opt[n,maxn];代码fori:=1tondoforj:=itomaxndoBeginopt[i,j]:=value[1..j];fork:=i-1toj-1doifopt[i,j]max(opt[i-1,k],value[k+1..j])thenopt[i,j]:=max(opt[i-1,k],value[k+1..j]);End;乘积最大国际数学联盟确定的“2000—世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛活动，你的好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N(N≤40)的数字串，要求选手使用M(M≤6)个乘号将它分成M+1个部分，找出一种分法，使得这M+1个部分的乘积最大。同时，为了帮助选手能够理解题意，主持人还举了如下一个例子：有一个数字串：312，当N=3，M=1时会有两种分法：⑴3×12=36⑵31×2=62这时，符合题目要求的结果是：31×2=62。现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。分析由于自然数位数的上限为40，乘号数的上限为6，因此最大乘积位数的上限接近42位。显然，运算任何整数类型都无法容纳如此之大的数据，只能采用高精度运算，限于篇幅，对于高精度的加法运算、乘法运算和比较大小的运算，这里不作介绍，只是对的乘号最佳插入方式进行探讨：假设s1‥si(2≤i≤n)中插入j个乘号，其中s1‥sk中插入了j-1个乘号，即乘式中的第j+1项为sk+1‥si(j≤k≤i-1)：分析设ans[i,j]——长度为i的数串中插入j个乘号的最大乘积（整型数组）。显然ans[i,0]=s1..si对应的整型数组；ans[i,j]=max{ans[k,j-1]×sk+1..si}（1≤i≤n，1≤j≤min{i-1,m}，j≤k≤i-1）ans[n,m]即为其解。分析由于乘式中第j+1项sk+1‥si为常量，因此要使得ans[i,j]最大，则s1‥sk中插入j-1个乘号的乘积必须最大；同样，为了寻找第j个乘号的最佳插入位置，必须一一查阅子问题ans[j,j-1]‥ans[i-1,j-1]的解。显然该问题具备无后效性、最优子结构的特征，适用于动态规划方法。状态的确定我们用ans[i,j]表示前i个字符插入j个乘号可以获得的最大值则有：ans[i,0]=s1..sians[i,j]=max{ans[k,j-1]×sk+1..si}(j≤k≤i-1)ans[n,m]即为其解。代码输入n，m和数串s；fori←1tondoans[i,0]←s1..si对应的整数数组；fori←2tondo{阶段：枚举数串的长度}forj←1tomin{i-1,m}do{状态：枚举长度为i的数串中插入的乘号个数}fork←jtoi-1do{决策：枚举第j个乘号的插入位置}beginnext←sk+1..si对应的整数数组；{计算第j+1项}ans[i,j]←max{ans[i,j]，ans[k,j-1]×next}；{计算状态转移方程}end；{for}输出最大乘积ans[n,m]；过河在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。分析从正面来考虑的话，这个问题是一个搜索性的问题，需要考虑从当前点出发可以跳到的所有点。然而从反面考虑的话，我们只需要考虑那些能到用一步到达当前点的所有点中，踩到石头数最小的那个。即opt[i]=min{opt[k](max{0,i-t}≤k≤i-s)}+bri[i];代码Fori←1tondoopt[i]:=10000000;opt[0]:=0;Fori←stoL+tdofork←max{0,i-t}toi-sdoifopt[k]+bri[i]opt[i]thenopt[i]:=opt[k]+bri[i];以上都是线性动规的一些例题，除了书的复制一题之外，它们的基础时间复杂度都是O(N2)装箱问题有一个箱子容量为maxv(正整数，maxv≤20000)，同时有n件物品(0≤n≤30)，每件物品有一个体积vi(正整数)。要求从这n件物品中任取若干件装入箱内，使箱子的剩余空间最小。分析这是一个最基础的背包问题，只需要考虑选取哪几个物品放入箱子，可以使得剩余体积最小。这道题的基本做法当然还是穷举放进背包的物品编号。若我们把取该物品记为1，不取该物品记为0，那么使用某种放入方式将对应一个2进制串，因此这类问题也被称为0-1背包问题.如果我们不从物品角度考虑，而是从体积角度考虑的话，就会发现，这个问题还可以被描述为，w[i]的体积是否能由这些物品得到。状态的确定我们用opt[i,j]（布尔）表示前i个物品是否能达到j体积。则opt[i,j]的值取决于前i-1个物品能否达到j体积，或者是前i-1个物品能否达到j-v[i]体积则有opt[i,j]=(opt[i-1,j-v[i]])or(opt[i-1,j])初值为opt[0,0]=true；其他都为false代码Fillchar(opt,sizeof(opt),0);opt[0,0]:=true;Fori:=1tondoforj:=0tomaxvdoifj=v[i]thenopt[i,j]:=(opt[i-1,j])or(opt[i-1,j-v[i]])elseopt[i,j]:=opt[i-1,j];采药辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”输入的第一行有两个整数T(1≤T≤1000)和N(1≤N≤100)，用一个空格隔开，T代表总共能够用来采药的时间，N代表山洞里的草药的数目。接下来的N行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。分析和上面一个问题一样，这个问题同样可以采用搜索解决，然而搜索的时间复杂度也同样相当的可怕。那我们可不可以借鉴一下上面的想法来解决这个问题呢？状态的确定答案是肯定的。类似地，我们用opt[i,j]表示前i个物体在j时间内的一个参数。但是我们在里面存的值并不是能否达到，而是在这个状态下可以达到的最大价值。但是状态的转移方程稍微有些差别，除了考虑opt[i-1,j-t[i]]和opt[i-1,j]之外，还要考虑opt[i,j-1](这样可以最后直接输出opt[n,maxt]从而省掉一次扫描)，即opt[i,j]表示前i个物体在j时间内可以达到的最大价值，注意这里包括不足j时间的情