当前位置:首页 >> 学科竞赛 >>

动态规划


动态规划

动态规划
? 什么是动态规划 ? 动态规划的条件 ? 动态规划的关键 ? 几种常见动态规划的种类 ? 例题分析

什么是动态规划
?

动态规划算法与分治法类似,其基本思想也是 将待求解问题分解成若干个子问题 ? 但是经分解得到的子问题往往不是互相独立的。 不同子问题的数目常常只有多项

式量级。在用 分治法求解时,有些子问题被重复计算了许多 次。 ? 如果能够保存已解决的子问题的答案,而在需 要时再找出已求得的答案,就可以避免大量重 复计算,从而得到多项式时间算法。

由此不难得出结论:动态 规划实质就是

下面这个数塔的例子将形象地向我们展示这 样的结论 ? 给你一个数字三角形, 形式如下: 1 2 3 8 5 18 14 2 1 10 找出从第一层到最后一层的一条 路,使得所经过的权值之和最小或 者最大.
?

当然,大家都很清楚的知道转移方程为 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。 ? 这是线性动态规划的经典例题。
?

代码
for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) { int mx = 1; for (int j = 1; j < i; j++) if (a[j] >= a[i]) mx = max(mx, f[j]); f[i] = f[j] + 1; } int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, f[i]); printf("%d\n", 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-l][k], value[k+1..j ]) ? (i-1≤k≤j-1); ? 最后输出opt[n,maxn];
?

代码
for (int i = 1; i <= n; i++) for (int j = i; j <= maxn; j++) { opt[i][j] = value[1..j]; for (int k = i - 1; k < j; k++) if (opt[i][j]>max(opt[i - 1][k], value[k + 1..j])) { opt[i][j] = max(opt[i - 1][k], value[k + 1..j]); } }

乘积最大
?

?

? ? ? ? ?

国际数学联盟确定的“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; for i←1 to n do ans[i][0]←s1..si对应的整数数组; for i←2 to n do {阶段:枚举数串的长度} for j←1 to min{i-1,m} do {状态:枚举长度为i的数串中插入的乘号个数} for k←j to i-1 do {决策:枚举第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≤is)}+bri[i];
?

代码
For i←1 to n do opt[i]=10000000; ? opt[0]=0; ? For i←s to L+t do ? for k←max{0,i-t} to i-s do ? if (opt[k]+bri[i]<opt[i]) ? 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]的值取决于前i1个物品能否达到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

代码
?
? ?

?
? ? ? ?

memset(opt, 0, sizeof(opt)); opt[0][0] = 1; for (int i = 1; i <= n; i++) for (int j = 0; j <= maxv; j++) if (j >= v[i]) { opt[i][j] = opt[i - 1][j] | opt[i - 1][j - v[i]]; } else opt[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时间的情 况。

代码
?

?
? ? ? ? ? ?

?

memset(opt, 0, sizeof(opt)); opt[0][0] = 1; for (int i = 1; i <= n; i++) for (int j = 1; j <= maxt; j++) if (j >= v[i]) { opt[i][j] = max{opt[i-1][j], opt[i-1][jt[i]]+value[i], opt[i][j-1]} } else opt[i][j] = max{opt[i-1][j], opt[i][j-1]}; printf("%d\n", opt[n][maxt]);

Dairy Queen
奶牛Bassie去DQ打工,遇到一个客人给了一张好大面值的 钞票,于是Bassie不得不为了给这位顾客找零而面对这样 一个问题:现在店里一共有n种硬币,对这些不同种的硬 币进行编号,编号为i的硬币面值为a[i] 。因为奶牛的手指 头是有限的,因此他只能向你求助啦。(已知总需找零数 为total)(1<=total<=1000,1<=n<=1000,1<=a[i]<=300) ? 求一共有多少种解决方案? ? 【输入】 ? 第一行为硬币总值total和硬币种类数n。 ? 以下n行为数值a[i],i=1,2,3...n ? 【输出】 ? 一行,解决方案数
?

分析
?
? ? ? ?

这道题目和上面的采药的区别仅仅在于,每个物 品可以无限次的取。 当然,这样的问题仍然可以用背包模型来解决, 我们将这种模型称为无限背包。 在这种情况下,我们只要把opt[i-1][j-a[i]]改成 opt[i][j-a[i]],即允许一种物品被取多次。 由于是计数,所以opt[i][j]=opt[i][j-a[i]]+opt[i-l][j]。 一个重要的优化:我们可以把opt数组压缩成长度 为total的一维数组,因为这样是不会影响结果的, 但可以大大降低它的空间复杂度。

状态的确定
? 我们用opt[j]表示硬币总面值为j时共有多

少种方法 ? opt[j]=opt[j]+opt[j-a[i]] (i=1,2,3..n)

代码
memset(opt, 0, sizeof(opt)); ? opt[0] = 1; ? for (int i = 1; i <= n; i++) ? for (int j = a[i]; j <= total; j++) ? opt[j] = opt[j] + opt[j - a[i]]; ? printf("%d\n", opt[total]);
?

多重背包
? ?

? ? ? ? ?

[问题题目] 有N种物品和一个容量为V的背包。第i种物品最多有 m[i]件可用,每件体积是v[i],价值是w[i]。求解将哪些 物品装入背包可使这些物品的体积总和不超过背包容 量,且价值总和最大。 [输入样例] 100 3 {maxv,n} 70 40 20 {v1,v2,……,vn} 50 40 30 {w1,w2,……,wn} 123 {m1,m2,m3……,mn}

分析
本题和无限背包问题很类似。基本的方程只需将 无限背包问题的方程略微一改即可,因为对于第i 种物品有m[i]+1种策略:取0件,取1件……取 m[i] 件。令 f[i][v] 表示前 i 种物品恰放入一个容量为 v 的 背包的最大价值,则:f[i][v]=max{f[i-1][v-k×v[i]]+ k×w[i] | 0<=k<=m[i]}。时间复杂度是O(V×∑m[i])。 ? 另一种好想好写的基本方法是转化为0-1有限背包 求解:把第i种物品换成m[i]件该物品,即转化成 了物品数为∑m[i]的0-1有限背包问题,直接求解, 复杂度仍然是O(V×∑m[i])。但是我们期望将它转 化为有限背包问题之后能够降低时间复杂度。
?

分析
?

?

应用二进制的思想,我们考虑把第i种物品换成若干件物品 ,使得原问题中第i种物品可取的每种策略——取0..m[i]件 ——均能等价于取若干件代换以后的物品。另外,取超过 m[i]件的策略必不能出现。方法是:将第i种物品分成若干 件物品,其中每件物品有一个系数,这件物品的体积和价 值均是原来的体积和价值乘以这个系数。使这些系数分别 为 1,2,4,...,2^(k-1),m[i]-2^k+1,且k是满足m[i]-2^k+1>0的最 大整数。 例如,如果m[i]为13,就将这种物品分成系数分别为1,2,4,6 的四件物品。分成的这几件物品的系数和为m[i],表明不 可能取多于m[i]件。另外这种方法也能保证对于0..m[i]间的 每一个整数,均可以用若干个系数的和表示。这样就将第i 种物品分成了(log m[i])种物品,将原问题转化为了复杂度 为O(V×∑log m[i])的有限背包问题,是很大的改进。

?

?
? ?

?
? ?

?
? ?

?
? ?

?

k = 0; //转化后物品的个数 for(int i = 1; i <= n; i++) { //对第i件物品进行组合 int t = 1; while (m[i] > 0) { if (m[i] >= t) { k++; v1[k] = v[i] * t; w1[k] = w[i] * t; m[i] = m[i] - t; t <<= 1; } else { k++; v1[k] = v[i] * m[i]; w1[k] = w[i] * m[i]; m[i] = 0; } } }

代码

? ? ? ? ? ?

?

for (int i = 1; i <= n; i++) { //01背包,注意n是转化后 的物品个数 for (int j = maxv; j >= v[i]; j--) { if (opt[j - v1[i]] + w1[i] > opt[j]) opt[j] = opt[j - v1[i]] + w1[i]; if (opt[j] > best) best = opt[j]; } 代码 printf("%d\n", best);

? 以上都是背包问题的一些

例题,他们的基础时间复 杂度都是O(mn)的

最小代价子母树
问题描述: 有n堆沙子排成一排,每堆沙子有一个数量,例 如:13 7 8 16 21 4 18。任意2堆相邻的沙子 可以进行合并,将两堆沙子合并为一堆时,两 堆沙子数量的和称为合并这两堆沙子的代价。 经过不断的归并,最后将这些沙子归为一堆, 而全部归并代价的和称为总代价。例如上列数, 其中2种归并方案的代价为: ? 第1种的总代价为 20+24+25+44+69+87 = 267 第2种的总代价为 15+37+22+28+59+87 = 248 由此可见,不同的归并过程得到的总代价是不 一样的。 ? 问题:当n个数给出后,找出一种合理的归并方 法,使得总代价最小。
?

分析
?

?

(1)如果把归并1~4堆看成整个问题,则这个问题可以分 解为三个归并方案,每个归并方案包含1~2个子问题: ? ①先归并1~3;再与4归并 ? ②归并1~2,归并3~4;再归并 ? ③归并2~4;再与1归并 (2) 如果我们继续分析增加更多堆数进行归并的问题, 就会发现n个数归并时,会分解为n-1种类型: ? Case1: 归并第1堆,归并2~n堆;再最后归并 ? Case2: 归并1~2堆,归并3~n堆;再最后归并 ? …… ? Case n-1: 归并1~n-1堆,归并第n堆;再最后归并

分析
?

通过前面的分析,我们看到,归并代价实际上由 两部分组成: ? (1)归并树左右子树的最小代价之和 ? (2)归并树所有叶结点的权值之和 而对于opt数组中的子区间数值的取值大小, 我们 有两种渠道来获取: ? (1)利用普通的dp,枚举开始结点和区间长度 来进行DP ? (2)记忆化搜索

?

状态的确定
? 我们用opt[i,j]表示i-j区间合并成一堆的最小代价,

则有上面的结论有

? opt[i][j]=min{opt[i][k]+opt[k+1][j](k=i..j-1)}+value[i..j]; ? opt[i][i]=value[i];

代码
? ? ? ?

?
? ? ? ? ? ?

?
? ?

for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) opt[i][j] = 10001000; for (int i = 1; i <= n; i++) opt[i][i] = value[i]; a[0] = 0; for (int i = 1; i <= n; i++) v[i] = v[i - 1] + value[i]; for (int j = 2; j <= n; j++) for (int i = 1; i <= n - j + 1; i++) for (int k = i; k <= i + j - 2; k++) if (opt[i][i+j-1]>opt[i][k]+opt[k+1][i+j-1]+v[i+j-1]-v[i-1]) opt[i][i+j-1]=opt[i][k]+opt[k+1][i+j-1]+v[i+j-1]-v[i-1]; printf("%d\n", opt[1][n]);

Power
多瑞卡得到了一份有趣而高薪的工作。每天早晨他必须 关掉他所在村庄的街灯。所有的街灯都被设置在一条直 路的同一侧。 ? 多瑞卡每晚到早晨5点钟都在晚会上,然后他开始关灯。 开始时,他站在某一盏路灯的旁边。 ? 每盏灯都有一个给定功率的电灯泡,因为多端卡有着自 觉的节能意识,他希望在耗能总数最少的情况下将所有 的灯关掉。 ? 多端卡因为太累了,所以只能以1m/s的速度行走。关灯 不需要花费额外的时间,因为当他通过时就能将灯关掉。 ? 编写程序,计算在给定路灯位置,灯泡功率以及多瑞卡 的起始位置的情况下关掉所有的灯的最少耗能。
?

Power
?

?
? ?

输入 第一行包含一个整数N,2≤N≤1000,表示该村庄路灯的数 量。 第二行包含一个整数V,1≤V≤N,表示多瑞卡开始关灯的路 灯号码。 接下来的N行中,每行包含两个用空格隔开的整数D和W, 用来描述每盏灯的参数,其中0≤D,W≤1000。D表示该路灯 与村庄开始处的距离(用米为单位来表示),W表示灯泡的功 率,每秒种该灯泡所消耗的能量数。路灯是按顺序给定的。 输出 一行,包含一个整数,即消耗能量之和的最小值。注意结 果不超过1,000,000,000。

? ?

分析
首先,我们必须明确这样一个决策:我们关 掉的灯必然是一个连续的区间,也就是说, 我们在路过的时候肯定会把灯顺手关掉,不 然肯定不是最优解。 ? 而在关掉一个区间之后,我们需要作出的决 定就是,回头关另外一边的灯还是继续朝当 前方向走关前面的灯。 ? 对于我们的最后求解区间i..j,有2种可能:最后 关第j盏灯,或者最后关第i盏灯。
?

分析
为了实现对这两种情况的记录,我们需要两个 数组,分别存放关完[i,j]区间的所有路灯后分 别站在两个端点时最小的电能消耗值。 ? 并且这两个数组中,[k][gdje](k=1.2.3...gdje-1) 区间的数值和[gdje][k](k=gdje+1...n)区间的数值 都是很容易确定的(gdje为开始位置)。 ? 在下面的动规过程中,我们只需要决策是需要 转向另外一边还是继续走下去就可以了。
?

状态的确定
? 我们用left[i][j]表示关完灯后人站在i点所消耗的最小电

能,用right[i][j]表示关完灯后人站在j点所消耗的最小 电能,则有 ? left[i][j]=min ? {left[i+l][j]+(value[1..i]+value[j+1..n])*(pos[i+1]-pos[i]), right[i+l][j]+(value[1][i]+value[j+1..n])*(pos[j]-pos[i])};
? right[i][j]=min ? {left[i][j-1]+(value[1..i-1]+value[j..n])*(pos[j]-pos[i])),

right[i][j-1]+(value[1..i-1]+value[j..n])*(pos[j]-pos[j-1])}

加分二叉树
?

? ? ? ? ?

设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中 数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正 整数),记第i个节点的分数为di,tree及它的每个子树都有一 个加分,任一棵子树subtree(也包含tree本身)的加分计算方 法如下: (subtree的左子树的加分)×(subtree的右子树的加分)+ subtree的根的分数 若某个子树为空,规定其加分为1,叶子的加分就是叶节点 本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树 tree。要求输出; (1)tree的最高加分 (2)tree的前序遍历

加分二叉树
? ? ? ? ? ? ?

?

【输入格式】 第1行:一个整数n(n<30),为节点个数。 第2行:n个用空格隔开的整数,为每个节点的分数(分数<100) 【输出格式】 第1行:一个整数,为最高加分(结果不会超过4,000,000,000)。 第2行:n个用空格隔开的整数,为该树的前序遍历。 【输入样例】 ? 5 ? 5 7 1 2 10 输出样例 ? 145 ? 31245

分析
我们可以发现这道题目给我们提供了一 段序列,我们需要做的就是每次选取一 个断开的点,然后把问题递归地求解就 可以了。 ? 这就为我们的动规提供了条件:具有最 优子结构性质。 ? 我们需要做出的决策,仅仅是从当前序 列中选取一个点作为当前子树的根节点, 所以动规的转移是O(n)的。
?

状态的确定
?

我们用opt[i][j]表示在[i..j]区间内可以获得的最大 加分,用root[i][j]表示[i..j]范围内选取哪个结点 作为根时可以获得最大加分。 对区间[i,j](i>j),我们定义opt[i][j]=1;

?

?
?

则有:
opt[i][j]=max

?
?

{opt[i][k-1]*opt[k+1][j]+value[k] | k=i,i+1,i+2..j}
root[i][j]为对应的k值

?

?
? ? ? ? ? ?

int search(int l, int r) { if (opt[l][r] != 0) return opt[l][r]; for (int i = l; i <= r; i++) if (search(l, i - 1) * search(i + 1, r) + value[i] > opt[l][r]) { opt[l][r] = search(l, i - 1) * search(i + 1, r) + value[i]; root[l][r] = i; } } memset(opt, 0, sizeof(opt)); for (int i = 1; i <= n + 1; i++) opt[i][i - 1] = 1; for (int i = 1; i <= n; i++) opt[i][i] = value[i]; int Ans = search(1, n);

代码

? ? ? ?

? 上面几道题是区间动态规划

的一些例题,它们的基础时 间复杂度都是O(N3)的

聚会的快乐(Party)
?

你要组织一个由你公司的人参加的聚会。你希望聚会非常 愉快,尽可能多地找些有趣的人。但是劝你不要同时邀请 某个人和他的上司,因为这可能带来争吵。给定N个人 (姓名,他幽默的系数,以及他上司的名字),找到能使 幽默系数和最大的若干个人。 输入 第一行一个整数N(N<100)。接下来有N行,每一行描 述一个人,信息之间用空格隔开。姓名是长度不超过20的 字符串。幽默系数是在0到100之间的整数 输出 邀请的人最大的幽默系数和

? ?

? ?

分析
?

?

?

仔细看过这个问题之后,会发现这道题目和我们上面 遇到的一些类型的动态规划都有点区别:它的数据并 不是以线性或者表格的形式, 而是以树的形式进行 存储的。 可以发现,这道题目中的关系可以简单地描述为:在 一棵树中,父亲结点和儿子结点不可以同时选取。而 每个结点有一个权值,在满足上述条件的情况下求出 可以选取出的最大值。 这就是我们所说的树形动态规划。由于树本身的递归 性质,我们使用记忆化搜索的方法来完成子问题答案 的存储。

状态的确定
? 显然,对于每个结点我们需要记录当前结点是否被取到, ?

?

?
? ?

?
?

以及在该种情况下该子树所能获得的最大幽默系数。 因此,我们定义opt[1][i]表示在编号为i的结点必取的情况下 以i为根的子树所能获得的最大快乐值;相应地,opt[0][i]表 示在编号为i的结点不取的情况下以i为根的子树所能获得的 最大幽默系数。 则根据题目中的要求,我们有 opt[1][i]=Σopt[0][k](k为所有i的子结点的编号) opt[0][i]=Σmax{opt[0][k],opt[1][k]}(k为所有i的子结点的编号) w数组用来存储边; r[i]存放编号为i的结点的儿子数; d[i]中存放编号为i的结点的在w数组中最后一条边的编号, 其中d[0]=0;d[i]=d[i-1]+r[i];

? ? ? ? ? ? ? ? ? ? ? ? ?

int search(int flag, int lab) { //记忆化搜索 if (opt[flag][lab] != 0) return opt[flag][lab]; int p = (flag == 1) ? value[lab] 0; for (int i = d[lab - 1]; i <= d[lab]; i++) if (flag == 1) p += search(0, w[i]); else p += max(search(0, w[i]), search(1, w[i])); opt[flag][lab] = p; return p; } memset(d, 0, sizeof(d)); for (int i = 1; i <= n; i++) d[i] = d[i - 1] + r[i]; ans = max(search(1, root), search(0, root));

代码

二*苹果树
? ? ? ?

有一棵苹果树,如果树枝有分叉,一定是分2叉(就 是说没有只有1个儿子的结点) 这棵树共有N个结点(叶子点或者树枝分叉点),编 号为1-N,树根编号一定是1。 我们用一根树枝两端连接的结点的编号来描述一根树 枝的位置。下面是一颗有4个树枝的树 现在这颗树枝条太多了,需要剪枝。但是一些树枝上 长有苹果。给定需要保留的树枝数量,求出最多能留 住多少苹果。

二*苹果树
?
? ?

输入格式 第1行2个数,N和Q(1<=Q<= N,1<N<=100)。N表示 树的结点数,Q表示要保留的树枝数量。 接下来N-1行描述树枝的信息。每行3个整数,前两个 是它连接的结点的编号。第3个数是这根树枝上苹果 的数量。 每根树枝上的苹果不超过30000个。
输出格式 一个数,最多能留住的苹果的数量。

? ?

分析
同样,这道题目给出的数据是以树形结构 连接的。 ? 而且这道题很明确的告诉我们:每个结点 只可能是叶节点或者拥有两个儿子。 ? 因此,我们可以讨论每个结点伸出的两个 树枝的剪枝情况,并且仍然用记忆化搜索 完成。
?

状态的确定
? 我们用opt[i][j]表示编号为i的结点作为根的子树中

保留j个树枝可以获得的最大苹果数。 ? 状态转移方程为: ? opt[i][j]:=max ? opt[i.rc][j-1]+value[i][i.rc], (剪掉左枝) ? opt[i.lc][j-1]+value[i][i.lc],(剪掉右枝) ? max{opt[i.lc][k]+opt[i.rc][j-2-k] +value[i][i.lc]+value[i][i.rc]}(0<=k<=j-2) (左枝和右 枝都不剪)

? ? ? ?

?
? ? ? ? ? ?

?
?

int search(int lab, int num) { if (opt[lab][num] != 0) return opt[lab][num]; if (lc[lab] == 0 || num == 0) return 0; int l = lc[lab], r = rc[lab]; if (search(r,num-1)+value[i][r]>opt[lab][num]) opt[lab][num]=opt[r][num-1]+value[i][r]; if (search(l,num-1)+value[i][l]>opt[lab][num]) opt[lab][num]=opt[l][num-1]+value[i][l]; for (int i = 0; i <= num-2; i++) if (search(l,i)+search(r,num-2-i)+value[i][l]+value[i][r]>opt[lab][num]) opt[lab][num]=opt[l][i]+opt[r][num-2-i]+value[i][l]+value[i][r]; return opt[lab][num]; }

代码

选课
?

?

[问题描述] 在大学里每个学生,为了达到一定的学分,必须从很 多课程里选择一些课程来学习,在课程里有些课程必 须在某些课程之前学习,如高等数学总是在其它课程 之前学习。现在有N门功课,每门课有个学分,每门 课只有一门或没有直接先修课(若课程a是课程b的先 修课即只有学完了课程a,才能学习课程b)。一个学 生要从这些课程里选择M门课程学习,问他能获得的 最大学分是多少?

选课
?

?
?

?

?

输入: 第一行有两个整数N,M用空格隔。 (1<=N<=200,1<=M<=150) 接下来的N行,第i+1行包含两个整数ki和si,ki表示 第i门课的直接先修课,si表示第i门课的学分。若 ki=0表示没有直接先修课(1<=ki<=N, 1<=si<=20)。 输出: 只有一行,选M门课程的最大得分。

分析
同样,这道题目给出的数据是以树形结构 连接的。 ? 这题比苹果树多了一个步骤就是把一棵多 叉树转化为二叉树。 ? 读入数据时把二叉树建好:把一门课的先 修课作为它的父亲。一个结点的第一个孩 子作为父节点的左子树,其它孩子作为第 一个孩子的右子树。
?

状态的确定
? F[x][y]:表示节点x取y门课得最高学分,则
? F[x][y]=max{f[x.r][y], f[x.l][k-1]+x.v+f(x.r,y-k)|k=1,2,..y} ? f[x.r][y]:表示不选课程x,右孩子选k门课。 ? f[x.l][k-1]+x.v(课程x的学分) :表示选了课程x,左孩子

选k-1门课,共k门课。 ? f (x.r,y-k)表示右孩子只能选y-k门课。 ? 标程中节点-1表示空节点,0是根节点,1-n是n门可 选课程的节点。

?

?
? ? ? ? ? ?

?
? ?

void treedp(int x, int y) { if (f[x][y] > 0) return; treedp(a[x].r, y); //只有右子树的情 f[x][y] = f[a[x].r][y]; for (int k = 1; k <= y; k++) { //左右子树都有的情况 treedp(a[x].l, k - 1); treedp(a[x].r, y - k); if (f[x][y] < f[a[x].l][k - 1] + f[a[x].r][y - k] + a[x].v) f[x][y] = f[a[x].l][k - 1] + f[a[x].r][y - k] + a[x].v } }

代码

? 这些题是树形动态规划的典

型例题,类似的题目还有很 多,在这就不一一列举了

? 看完了这么多题目之后,

我们再来总结一下动态 规划的重点和难点

上面所有的问题都可以用穷举和搜索来解决, 但是比较之下动态规划却有很明显的时间优 势,采取的是牺牲空间换取时间的方法。 ? 在整个思考过程中,我们通常是采取换一个 角度来考虑问题的方法,巧妙地把其中的某 个参数转化成维度,从而将原本需要大量重 复计算的东西存下来,随时方便调用。 ? 因此,想要用好动态规划,必须得学会转化 思考角度,充分利用空间来节省时间。
?

同时,我们也必须看到,在DP问题的思 考过程中,最关键的两个东西就是 ? 状态的确定和转移方程。
?

?

这也是在运用动态规划的过程中的难点 之一。

?

当然,动态规划也不是万能的。比如之 前提到的数塔问题中,如果是要求一条 路径使得最终结果最接近0的话,那么 DP也无能为力了。 只有在满足前面所提到的最优子结构性 质和不具有后效性的两个前提下,动态 规划才能发挥它的作用。

?

The End
Thanks


相关文章:
动态规划(DP)的使用条件
,但从空间复杂度来看,动态规划算法为 O(n2),而搜索 算法为 O(n),搜索算法反而优于动态规划算法。选择动态规划算法是因 为动态规划算法在空间上可以承受,而搜索...
4种常见的动态规划模型
(三)、区间类模型 区间类模型的动态规划, 一般是要求整段区间的最优值, 子问题一般是把区间分成两个 子区间。一般用二维数组表示状态,例如 f[i,j]表示从 i...
动态规划与静态规划的关系
动态规划与静态规划的关系 动态规划与静态规划(线性和非线性规划等)研究的对象本质上都是在若 干约束条件下的函数极值问题。 两种规划在很多情况下原则上可以相互 ...
动态规划的很经典的教程
动态规划的很经典的教程_电脑基础知识_IT/计算机_专业资料。动态规划的很经典的教程引言:本人在做过一些题目后对 DP 有些感想,就写了这个总结: 第一节 动态规划...
※动态规划经典教程
动态规划经典教程 Directory 1.1 下降/非降子序列问题: 例题 1 拦截导弹例题二 合唱队形※例题 3 Buy Low Buy Lower 例题 4 船 1.2 背包问题 例题 5 装...
动态规划算法原理与应用
3.2 动态规划问题中的术语 阶段: 把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求 解,过程不同,阶段数就可能不同.描述阶段的变量称为阶段变量。...
动态规划算法举例分析
动态规划算法介绍 基本思想是将待求解问题分解成若干子问题,先求解子问题,最后用这些子 问题带到原问题, 与分治算法的不同是,经分解得到的子问题往往是不是相互...
动态规划理论(精华)
动态规划理论(精华)_IT/计算机_专业资料。动态规划理论一.动态规划的逆向思维法动态规划是一种思维方法,没有统一的、具体的模式。动态规划可以从多方面 去考察,不...
动态规划-最优化原理和无后效性
动态规划-最优化原理和无后效性_互联网_IT/计算机_专业资料。动态规划-最优化原理和无后效性动态规划-最优化啊原理和无后效性 上面已经介绍了动态规划模型的基本...
动态规划的特点及其应用
§1 动态规划的本质动态规划是在本世纪 50 年代初,为了解决一类多阶段决策问题而诞生的。那么, 什么样的问题被称作多阶段决策问题呢? §1.1 多阶段决策问题说...
更多相关标签:
动态规划算法 | 动态规划原理及应用 | 动态规划 背包问题 | 贪心算法 | 动态规划算法例题 | 动态规划法 | 2038年问题 | 动态规划 最短路径 |