2025/3/281DynamicProgramming2025/3/282Dynamicprogrammingvs.divide-and-conquer

Divide-and-conqueralgorithmssplitaproblemintoseparatesubproblems,solvethesubproblems,andcombinetheresultsforasolutiontotheoriginalproblem.Divide-and-conqueralgorithmscanbethoughtofastop-downalgorithmsIncontrast,adynamicprogrammingalgorithmproceedsbysolvingsmallproblems,thencombiningthemtofindthesolutiontolargerproblemsDynamicprogrammingcanbethoughtofasbottom-upStoreandnotstoresolutionstosubproblems2025/3/283ThreebasiccomponentsThedevelopmentofadynamicprogrammingalgorithmhasthreebasiccomponents:Arecurrencerelation(fordefiningthevalue/costofanoptimalsolution);Atabularcomputation(forcomputingthevalueofanoptimalsolution);Abacktracingprocedure(fordeliveringanoptimalsolution).2025/3/284ExamplesofDynamicProgrammingAlgorithmsLongestpathinDAGComputingbinomialcoefficientsEditdistanceKnapsackChainmatrixmultiplicationall-pairsshortestpathsTravelingsalesman2025/3/285LongestpathinDAGProblem:GivenaweighteddirectedacyclicgraphG=(V,E),anvertexv,whereeachedgeisassignedanintegerweight,findalongestpathingraphG.2025/3/286LongestpathinDAGdilg(v):thelongestpathendingwithv.dilg(D),dilg(B),dilg(C)dilg(D)=max{dilg(B)+1,dilg(C)+3}Foranyvertexv,dilg(v)=max(u,v)∈E{dilg(u)+w(u,v)}2025/3/287LongestpathinDAGDplongestpath(G)Initializealldilg(.)valuesto∞;LetSbethesetofverticeswithindegree=0;ForeachvertexvinSdodilg(v)=0;3.Foreachv∈V\SinTopologicalSortingorderdo

dilg(v)=max(u,v)∈E{dilg(u)+w(u,v)}4.Returnthedilg(.)withmaximumvalue.2025/3/288ComputingBinomialCoefficients

Abinomialcoefficient,denotedC(n,k),isthenumberofcombinationsofkelementsfromann-elementset(0≤k≤n).RecurrencerelationC(n,k)=C(n-1,k-1)+C(n-1,k)forn>k>0,andC(n,0)=C(n,n)=12025/3/289Dynamicprogrammingsolution:Recordthevaluesofthebinomialcoefficientsinatableofn+1rowsandk+1columns,numberedfrom0tonand0tokrespectively.

0123…k-1k01 111 211 311 … k11 … n-11 n12025/3/2810Dynamicprogrammingsolution:Recordthevaluesofthebinomialcoefficientsinatableofn+1rowsandk+1columns,numberedfrom0tonand0tokrespectively.

0123…k-1k01 111 2121 311 … k11 … n-11 n12025/3/2811Dynamicprogrammingsolution:Recordthevaluesofthebinomialcoefficientsinatableofn+1rowsandk+1columns,numberedfrom0tonand0tokrespectively.

0123…k-1k01 111 2121 31331 … k11 … n-11 n12025/3/2812Dynamicprogrammingsolution:Recordthevaluesofthebinomialcoefficientsinatableofn+1rowsandk+1columns,numberedfrom0tonand0tokrespectively.

0123…k-1k01 111 2121 31331 … k11 … n-11C(n-1,k-1)C(n-1,k) n12025/3/2813Dynamicprogrammingsolution:Recordthevaluesofthebinomialcoefficientsinatableofn+1rowsandk+1columns,numberedfrom0tonand0tokrespectively.

0123…k-1k01 111 2121 31331 … k11 … n-11C(n-1,k-1)C(n-1,k) n1C(n,k)2025/3/2814ComputingBinomialCoefficients

Binomial(n,k)1.for

i=0tondo

C[i,0]=1;2.forj=0tomin(i,k)do

C[j,j]=1;3.for

i=0tondoforj=0tomin(i,k)do

C[i,j]=C[i-1,j-1]+C[i-1,j];4.returnC[n,k].

2025/3/2815EditDistanceThedistancebetweenstrings:alignmentAlignment:awayofwritingthestringsoneabovetheother.

The“－”indicatesa“gap”;anynumberofthesegapcanbeplacedineitherstring.Thecostofanalignmentisthenumberofcolumnsinwhichthelettersdiffer.2025/3/2816EditDistanceCost:3Cost:5The

editdistancebetweentwostringsisthecostoftheirbestpossiblealignment.2025/3/2817EditDistanceSubproblemE[i,j]rightmostcolumnE(i,j)E(i-1,j)E(i,j)=1+E(i-1,j)RelationshipE(i,j)E(i,j-1)E(i,j)=1+E(i,j-1)RelationshipE(i,j)E(i-1,j-1)E(i,j)=1/0+E(i-1,j-1)Relationship2025/3/2818EditDistanceIfx[i]=x[j]thendiff(i,j)=0,otherwisediff(i,j)=1.E(0,j)=j.E(i,0)=i.2025/3/2819EditDistanceTheanswerstoallthesubproblemsE(i,j)formatwo-dimensionaltable.2025/3/2820EditDistanceDPEditDis(x[1..m],y[1..n])Fori=0tomdoE(i,0)=i;2.Forj=1tondoE(0,j)=j;3.Fori=1tomdoforj=1tondoE(i,j)=min{E(i-1,j)+1,E(i,j-1)+1,E(i-1,j-1)+diff(i,j)}4.ReturnE(m,n).Runningtime:O(mn)2025/3/2821ThefindingofsubproblemsisanimportantstepinDynamicprogramming.SubproblemschoosingCommonlyusedmethods:Theinputisx1,x2,…,xn.asubproblemisx1,x2,…,xi.HowmanysubproblemsforthiscaseO(n)2025/3/2822Subproblemschoosing2.Theinputisx1,x2,…,xn,andy1,y2,…,ym.asubproblemisx1,x2,…,xiandy1,…,yj.HowmanysubproblemsforthiscaseO(mn)2025/3/2823Subproblemschoosing3.Theinputisx1,x2,…,xn.asubproblemisxi,xi+1,…,xj.HowmanysubproblemsforthiscaseO(n2)2025/3/2824Subproblemschoosing3.Theinputisarootedtree.asubproblemisarootedsubtree.IfthetreehasnnodesHowmanysubproblemsarethere2025/3/2825KnapsackHisbag(or.knapsack.)willholdatotalweightofatmostWpounds.Therearenitemstopickfrom,ofweightw1,…,wnandvaluev1,…,vn.What'sthemostvaluablecombinationofitemshecanfitintohisbag2025/3/2826KnapsackTwoversionsoftheproblemeachitem:unlimitedquantityeachitem:onlyoneKnapsackwithrepetitionKnapsackwithoutrepetitionW=102025/3/2827KnapsackKnapsackwithoutrepetitionWhatarethesubproblemsK(w)K(w-wi)isthemaximumoneforallitems.smallerknapsackcapacitiesw≤Wfeweritems(forinstance,items1,2,…,j,forj≤n).K(w,j)=maximumvalueachievableusingaknapsackofcapacitywanditems1,…,j.2025/3/2828KnapsackKnapsackwithoutrepetitionWhatarethesubproblemsK(w,j)=maximumvalueachievableusingaknapsackofcapacitywanditems1,…,j.K(W,n)istheanswer.HowtogetsubproblemK(w,j)intermsofsmallersubproblemsK(w,j)=max{K(w-wj,j-1)+vj,K(w,j-1)}w≥wjK(0,j)=0,K(w,0)=0.w<wjK(w,j)=K(w,j-1)2025/3/2829KnapsackDPKnapsacknorepe(item1,…,itemn;w1,…,wn;v1,…,vn,W)Forj=1tondoK(0,j)=0;Forw=0toWdoK(w,0)=0;Forj=1tondoforw=1toWdoifwj>wthenK(w,j)=K(w,j-1);elseK(w,j)=max{K(w,j-1),K(w-wj,j-1)+vj};4.ReturnK(W,n).Runningtime:O(nW)2025/3/2830Knapsack0…w-wj…w…W00…0…0….0：：…j-1

0…K[w-wj,j-1]K[w,j-1]j0…K[w,j]n0…goal2025/3/2831Chainmatrixmultiplicationtheorderofmultiplicationsmakesabigdifferenceinthefinalrunningtime!ComputeA1×A2×…×An,A1:m0×m1A2:m1×m2…An:mn-1×mn.Howdowedeterminetheoptimalorder2025/3/2832ChainmatrixmultiplicationMatrixmultiplicationBinarytreeforatreetobeoptimal,itssubtreesmustalsobeoptimal.WhatarethesubproblemscorrespondingtothesubtreesAi×Ai+1×…×AjC(i,j)=minimumcostofmulitiplyingAi×Ai+1×…×Aj.1≤i≤j≤n2025/3/2833ChainmatrixmultiplicationC(i,j)=minimumcostofmulitiplyingAi×Ai+1×…×Aj.1≤i≤j≤nHowtogetsubproblemC(i,j)intermsofsmallersubproblemsforakbetweeniandj,Ai×…×AkandAk+1×…×AjC(i,k)C(k+1,j)C(i,j)C(i,k)C(k+1,j)j≥ij=iC(i,i)=0.2025/3/2834ChainmatrixmultiplicationDpmatrixmul(A1,A2,..,An)Fori=1tonC(i,i)=0;2.Fors=1ton-1dofori=1ton-sdoj=i+s;C(i,j)=min{C(i,k)+C(k+1,j)+mi-1.mk.mj,i≤k<j};3.ReturnC(1,n).Runningtime:O(n3)2025/3/2835AllpairsshortestpathIsthereisagoodsubproblemforcomputingdistancesbetweenallpairsofverticesinagraphShortestpathbetweenu,vu,w1,w2,…,wh,vSupposewedisallowintermediatenodesaltogether.Thenwecansolveall-pairsshortestpathsatonce:theshortestpathfromutovissimplythedirectedge(u,v),ifitexists.2025/3/2836AllpairsshortestpathD(k):allow1,2,…,ktobeintermediatevertices.dij(k)=min{dij(k-1),dik(k-1)+dkj(k-1)}fork

1,dij(0)=wijHowtogetsubproblemdij(k)intermsofsmallersubproblemsijkdij(k-1)dik(k-1)dkj(k-1)2025/3/2837AllpairsshortestpathDpallpairst