动态规划 试题分析

《动态规划 试题分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划试题分析与动态规划什么是动态规划动态规划的条件动态规划的关键几种常见动态规划的种类例题分析什么是动态规划动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。由此不难得出结论：动态规划实质就是记忆化搜索下面这个数塔的例子将形象地向我们展示这样的结论给你一个数字

2、三角形,形式如下:1238518142110找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.当然，大家都很清楚的知道转移方程为opt[i,j]=max{opt[i-1,j],opt[i-1,j-1]}+a[i,j]，边界条件特殊处理即可。但只要仔细想想就会发现，这不过是一个加了强力减枝的记忆划搜索而已，因为每个点我们只记录到当前节点的最优解，因此省去了大量的重复计数和明显不是最优解的情况，从而使运行速度有了极大的优化动态规划的条件而在求解的过程中一道能使用动规解决的题必须具备以下几个条件无后效性,即

3、某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。满足最优子结构性质，即一个问题的最优解必须是在子问题取得最优解的情况下决策出来的动态规划的过程可以简单地描述为找出最优解的性质，并刻画其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。动态规划的关键有明确的状态状态转移方程清晰正确几种常见动规的种类线性动规背包问题区间动规树形动规下面让我

4、们通过几个例子来了解这些基本动规的思考方法拦截导弹（Noip2002）某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹。状态的确定状态的表示——f[i]，表示当第i个导弹必须拦截时，前i个导弹中最多能拦截多少。每个导弹有一定的高度，当前状态就是以第

5、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]+1>f[i])thenf[i]:=f[

6、j]+1;Ans:=0;Fori:=1tondoiff[i]>ansthenans:=f[i];Writeln(ans);书的复制现在要把maxn本有顺序的书分给n个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。输入第一行两个整数maxn,n；（n<=maxn<=100）第二行maxn个整数，第i个整数表示第i本书的页数。输出共n

7、行，每行两个正整数，第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:=1to

8、ndoforj:=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—世界数学年