【文档说明】C案例04动态规划课件.ppt，共(57)页，461.012 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-2849.html

以下为本文档部分文字说明：

2022/11/121第四讲动态规划（Dynamicprogramming）2022/11/122一、经典问题：数塔问题有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。2022/11/123用暴力

的方法，可以吗？2022/11/124这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（2^30=1024^3>10^9=10亿）。试想一下：2022/11/125拒绝暴力，倡导和谐～2022/11/126从顶点出发

时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。如数字2，只要选择它下面较大

值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。考虑一下：2022/11/127思路：从倒数第二行起，按照状态转移方程dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])

+val[i][j]向上递推，直到val[1][1]，此时dp[1][1]就是结果2022/11/128二、经典问题：最长有序子序列[问题描述]找出由n个元素组成的序列的最长有序子序列长度及其中一个最长有序子序列（注：这里有序指非递减顺序，且不要求子序列连续）。例如，对于序

列[3,7,1,5,9,3]，其中最长有序子序列长度为3，这样的子序列有：[3,7,9]、[1,5,9]、[3,5,9]。2022/11/129二、经典问题：最长有序子序列2022/11/1210二、经典问题：最长有序子序列2022/11/1211二、经典问题：最长有序子序

列2022/11/1212三1160FatMouse'sSpeedProblemDescriptionFatMousebelievesthatthefatteramouseis,thefasteritruns.Todisprovethis,youwanttotakethedataonac

ollectionofmiceandputaslargeasubsetofthisdataaspossibleintoasequencesothattheweightsareincreasing,butthespeed

saredecreasing.InputInputcontainsdataforabunchofmice,onemouseperline,terminatedbyendoffile.Thedataforaparticularm

ousewillconsistofapairofintegers:thefirstrepresentingitssizeingramsandthesecondrepresentingitsspeedincen

timeterspersecond.Bothintegersarebetween1and10000.Thedataineachtestcasewillcontaininformationforatmost1000mice.Twomicemayhavethesameweight,the

samespeed,oreventhesameweightandspeed.2022/11/1213三1160FatMouse'sSpeedOutputYourprogramshouldoutputaseque

nceoflinesofdata;thefirstlineshouldcontainanumbern;theremainingnlinesshouldeachcontainasinglepositiveinteger(eachoner

epresentingamouse).Ifthesenintegersarem[1],m[2],...,m[n]thenitmustbethecasethatW[m[1]]<W[m[2]]<...<W[m[n]]andS[m[1]]>S[

m[2]]>...>S[m[n]]Inorderfortheanswertobecorrect,nshouldbeaslargeaspossible.Allinequalitiesarestrict:weightsmustbestrictlyin

creasing,andspeedsmustbestrictlydecreasing.Theremaybemanycorrectoutputsforagiveninput,yourprogramonlyneedstofindone.

2022/11/1214三1160FatMouse'sSpeedSampleInput6008130060002100500200010004000110030006000200080001400600012002000

1900SampleOutput445972022/11/1215三1160FatMouse'sSpeed解题思路：题目要求找到的体重递增，速度递减老鼠，先把老鼠的体重进行升序排序然后算出速度的最长递减子序列。2022/11/1216四1087SuperJumping!Jumping!Juping

!ProblemDescriptionNowadays,akindofchessgamecalled“SuperJumping!Jumping!Jumping!”isverypopularinHDU.Maybeyouareagoodboy,a

ndknowlittleaboutthisgame,soIintroduceittoyounow.Thegamecanbeplayedbytwoormorethantwoplayers.Itconsistsofachessboard

（棋盘）andsomechessmen（棋子）,andallchessmenaremarkedbyapositiveintegeror“start”or“end”.Theplayerstartsfrom

start-pointandmustjumpsintoend-pointfinally.Inthecourseofjumping,theplayerwillvisitthechessmeninthepath,buteveryonemustjumpsfrom

onechessmantoanotherabsolutelybigger(youcanassumestart-pointisaminimumandend-pointisamaximum.).Andallplayerscannotg

obackwards.Onejumpingcangofromachessmantonext,alsocangoacrossmanychessmen,andevenyoucanstraightlygettoend-pointfromstart-point

.Ofcourseyougetzeropointinthissituation.Aplayerisawinnerifandonlyifhecangetabiggerscoreaccordingtohisjumpingsolu

tion.Notethatyourscorecomesfromthesumofvalueonthechessmeninyoujumpingpath.Yourtaskistooutputthemaximumvaluea

ccordingtothegivenchessmenlist.2022/11/1217四1087SuperJumping!Jumping!Juping!InputInputcontainsmultipletestcases.Eachte

stcaseisdescribedinalineasfollow:Nvalue_1value_2…value_NItisguarantiedthatNisnotmorethan1000andallvalue_iareintherangeof32-int.At

estcasestartingwith0terminatestheinputandthistestcaseisnottobeprocessed.OutputForeachcase,printthemaximumaccordingtorules,andoneline

onecase.2022/11/1218四1087SuperJumping!Jumping!Juping!SampleInput313241234433210SampleOutput4103解题思路？找序列中

最大升序子序列的和2022/11/1220动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=2022/11/1221但是经分

解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/

4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/42022/11/1222如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n

/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)2022/11/1223动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底

向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。2022/11/1224动态规划算法的基本要素一、最优子结构•问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。•在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的

最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。•利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。同一个问题可以有多

种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）2022/11/1225动态规划算法的基本要素二、重叠子问题•递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种

性质称为子问题的重叠性质。•动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。•通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划

算法只需要多项式时间，从而获得较高的解题效率。2022/11/1226动态规划算法的基本要素三、备忘录方法•备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时

查看，避免了相同子问题的重复求解。intLookupChain(inti，intj){if(m[i][j]>0)returnm[i][j];if(i==j)return0;intu=LookupChain(i，i)+Lookup

Chain(i+1，j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=LookupChain(i，k)+LookupChain(k+1，j)+p[i-1]*p[k]*p[j];if(t<u)

{u=t;s[i][j]=k;}}m[i][j]=u;returnu;}2022/11/1227五、经典问题：最长公共子序列ProblemDescriptionAsubsequenceofagivensequenceisthegivensequencew

ithsomeelements(possiblenone)leftout.GivenasequenceX=<x1,x2,...,xm>anothersequenceZ=<z1,z2,...,zk>isasubs

equenceofXifthereexistsastrictlyincreasingsequence<i1,i2,...,ik>ofindicesofXsuchthatforallj=1,2,...,k,xij=zj.Forexample,Z=<

a,b,f,c>isasubsequenceofX=<a,b,c,f,b,c>withindexsequence<1,2,4,6>.GiventwosequencesXandYtheproblemistofindthelengthofthemaximu

m-lengthcommonsubsequenceofXandY.Theprograminputisfromatextfile.Eachdatasetinthefilecontainstwostringsrepresentingthegivenseq

uences.Thesequencesareseparatedbyanynumberofwhitespaces.Theinputdataarecorrect.Foreachsetofdatatheprogramprintsonthestandardoutputthelengthofthemaxi

mum-lengthcommonsubsequencefromthebeginningofaseparateline.2022/11/1228五、经典问题：最长公共子序列HDOJ-1159：SampleInputabcfbcabfcabprogrammingcontestabcdmnpSa

mpleOutput4202022/11/1229最长公共子序列•若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z=

{B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。•给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。•给定2个序列

X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。2022/11/1230最长公共子序列的结构设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则(1)若xm=yn，则zk=xm=yn，且

zk-1是xm-1和yn-1的最长公共子序列。(2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。(3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长

公共子序列。因此，最长公共子序列问题具有最优子结构性质。2022/11/1231子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其

中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：jijiyxj

iyxjijijicjicjicjic;0,;0,0,0]}][1[],1][[max{1]1][1[0]][[2022/11/1232abcfbca111111b122222f122333c123334a12333

4b123344辅助空间变化示意图2022/11/1233计算最优值由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。voidLCSLength(in

tm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if

(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3

;}}}构造最长公共子序列voidLCS(inti，intj，char*x，int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1，j-1，x，b);cout<<x[i];}else

if(b[i][j]==2)LCS(i-1，j，x，b);elseLCS(i，j-1，x，b);}2022/11/1234算法的改进•在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这

3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。•如果只需要计算最长公共子序列的长度，则算法的空间需

求可大大减少。事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。2022/11/1235六、经典问题：1421搬寝室ProblemDescrip

tion搬寝室是很累的,xhd深有体会.时间追述2019年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了

.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬

完这次的疲劳度为(6-3)^2=9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.2022/11/1236六、经典问题：1421搬寝室Input每组输入数据有两行,第一行有两个数n,k

(2<=2*k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).Output对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.2022/11/1237六、经典问题：1421搬寝室SampleInput2113Samp

leOutput42022/11/1238第一感觉：根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？证明：假设四个从小到大的数：a、b、c、d，只需证明以下表达式成立即可：(a-b)^2+(c-d)^2<(a-c)^

2+(b-d)^2(a-b)^2+(c-d)^2<(a-d)^2+(b-c)^2……(略)2022/11/1239预备工作：排序！2022/11/1240第二感觉：对于一次操作，显然提的物品重量越接近越好，是不是可以贪心呢？请思考…考虑以下情况：1458什么结论？2022/11/12

41详细分析：从最简单的情况考虑：2个物品选一对，结论显然结论？4个物品选一对？（如何利用前面的知识）3个物品选一对，…n个物品选一对，…最终问题：n个物品选k对（n>=2k），如何？n个物品选二对，…2022/11/1242解题思路先对物品的重量进行排序，取

相邻的物品，将相邻的物品的差的平方另外存储，得到状态转移方程：dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+s[i]),s[i]是代表i,i+1这两个物品的疲惫度.因为s[i-1],s[i].代表的是ai-1,ai,ai+1的疲惫度，

中间共享了一个ai，所以第二项要用dp[i-2].2022/11/1243参考代码#include<iostream>#include<algorithm>usingnamespacestd;#defineINF0x7fffffffintdp[2000][2000],a[

2000],s[2000];intmain(){intn,k,i,j;while(scanf("%d%d",&n,&k)!=EOF){for(i=1;i<=n;i++)scanf("%d",&a[i]);sort(a,a+n+1);for

(i=1;i<=n;i++)for(j=1;j<=n/2;j++)dp[i][j]=INF;for(i=2;i<=n;i++)s[i]=(a[i]-a[i-1])*(a[i]-a[i-1]);for(i=2;i<=n;i++)for(j=1;j

<=i/2;j++)dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+s[i]);printf("%d\n",dp[n][k]);}return0;}2022/11/1244七、经典问题：1

058HumbleNumbersProblemDescriptionAnumberwhoseonlyprimefactorsare2,3,5or7iscalledahumblenumber.Thesequence1,2,3,4,5,6,7,

8,9,10,12,14,15,16,18,20,21,24,25,27,...showsthefirst20humblenumbers.Writeaprogramtofindandprintthenthelement

inthissequence2022/11/1245七、经典问题：1058HumbleNumbersInputTheinputconsistsofoneormoretestcases.Eachtestcaseconsistsofoneinteger

nwith1<=n<=5842.Inputisterminatedbyavalueofzero(0)forn.OutputForeachtestcase,printonelinesaying"Thenthhumblenumberisn

umber.".Dependingonthevalueofn,thecorrectsuffix"st","nd","rd",or"th"fortheordinalnumbernthhastobeusedlikeitisshowninthesampleoutput.2022/11/1246七

、经典问题：1058HumbleNumbers2022/11/1247算法分析：典型的DP!1->?1->2=min(1*2,1*3,1*5,1*7)1->2->3=min(2*2,1*3,1*5,1*7)1->2->3->4=min(2*2,2*3,

1*5,1*7)1->2->3->4->5=min(3*2,2*3,1*5,1*7)2022/11/1248状态转移方程？F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7)(n>i,j,k,m)特别的：i,j,

k,m只有在本项被选中后才移动2022/11/1249关键问题：这个题目的哪些经验值得我们借鉴？2022/11/1250八免费馅饼11762022/11/1251八免费馅饼1176ProblemDescription都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上

掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于

gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-

10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）2022

/11/1252八免费馅饼1176Input输入数据有多组。每组数据的第一行为以正整数n(0<n<100000)，表示有n个馅饼掉在这条小径上。在结下来的n行中，每行有两个整数x,T(0<T<100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。

n=0时输入结束。Output每一组输入数据对应一行输出。输出一个整数m，表示gameboy最多可能接到m个馅饼。提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。2022/11/1253八免费馅饼1176SampleInput651

41617272830SampleOutput42022/11/1254如何解决？请发表见解2022/11/1255解题思路有点类似于数塔Dp[t][i]=MAX(Dp[t-1][i-1],Dp[t-1][i],

Dp[t-1][i+1])+DATA[t][i];2022/11/1256自学题请大家自学课本P239最短路径问题P247插入乘号问题2022/11/1257如果各个子问题不是独立的，不同的子问题的个数只是多项式量

级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是——用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。小结：DP的基本思想