KEMBAR78
DP Notes Aditya Verma | PDF
Scribd
Upload
864 views104 pages

DP Notes Aditya Verma

The document discusses dynamic programming (DP) techniques, particularly focusing on recursion and memoization. It outlines various DP problems such as the 0-1 knapsack problem, subset sum, and equal sum partition, providing insights into their recursive and iterative solutions. The document emphasizes the importance of base conditions and initialization in solving these problems effectively.

Uploaded by

jeet
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
864 views104 pages

DP Notes Aditya Verma

The document discusses dynamic programming (DP) techniques, particularly focusing on recursion and memoization. It outlines various DP problems such as the 0-1 knapsack problem, subset sum, and equal sum partition, providing insights into their recursive and iterative solutions. The document emphasizes the importance of base conditions and initialization in solving these problems effectively.

Uploaded by

jeet
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 104
FOP OP EEEE EER ENEDDDDD PPVOEVD . > PEBD_wWrV: Scanned with ComScanner * = * Dynamic Programming * ke ~ DP= Enhanced Recursion foction cates calls itself with > = s o~ r Smaller inputs . an co, 38 Hat Ses > oe eed cess, is tecursion ==> asks for optim on = 2 Choice | choose — Recursion can be applied = a Recursive ——» Memoize ——> ar | a function Crop - dover’) Golem -up ~~ : - - > > + re mi » © Variations in DP problems = 0-1 knapsack 6) Unbound ed knapsack (5) Fibonacci (7) J J d Longest Grmmon Subsequence (/5) Longest Tnereasing Subsequence(o) kadane's Ayorithm (6) Matrix Chain Multiplication(7) DP on Trees (4) DP on mahix (/4.) Others (5) @O@®QGOOO9GO0° Total prodlen/ Variations = TI prblena Scanned with ComScanner 4 0-1 knapsack Problem i] Subset Sum 2] Equal Sum partition 3] Gunt of Subset Sum ¥] Minimum Subset sum difference $] Target sum 3] Number of Subsets with given difference HENS Fractional o/t Unbounded Greedy ) knapsack nap Sack. ble) Joi Is Ty Peg 8 4s vol]: | 4 5S 7 we 7 ( Capacity) (ala a eS SSS 90s nw rE ana Scanned with ComScanner —————E— ee AUC LLULLELELUL ELE tbo ee TUTTI be takeu .. item cow Th raconal Fgh, fran of 0" include that item oF i But in oft knapsack, either we have exclude the item , 4 vole instances of ifeuw. 4 unbounded Knapsack, we con take multiple inste: + wt CJ: - 245 output maxpregit. ? 7 Male: ad 60 {hieyare askso, wi Thy optima profit for every item (item) Y z f Choice Cues) (to choiee) SS) Hence thio bo a Cincue) Cexcwpe) problers 4 OP eo 3 + Recursive _, Meroizatim ——> Botrom -up solution (Tip- dow) Dp > Recursive de Storage Scanned with ComScanner (Aa COS OO — ° O/4 knapsack Recursion v Item (wi) x f the weight of the item > the capacity of the bag. ek Suppose can take — con't eanit. take take . £napsact int ‘madboffe(int wXl3, int val] , int capoctyR, int n) { W Bose Condition iF(n ==0 [I capacity ==0) yelurn 0; He if ( wt[h-i] ¢= capacity) catuin max( val Go-IH- koap sck tive» capacity at 07) na); > knapsack ( wt val Capacity, n-i)) ; alse if (wt [n-] > Capacity) * syetutn knapsack Cwt, Val, Capacity n-); Scanned with ComScanner rerneaonRNaDsaccateeee > cued b ttt 2 CCT AA How to think about the base condition 2 nO MOPEDS. SEGUE iette, Hage - CORCIN © Base condition —> “Think of the smallest valed input O)t Knapsack tep-deeen—Apprrade-Menvoi zation $0 th the recursive knapsack the variables that are changing > an 6) Copacity Se qpr these variabla only, we have te prepare Ha tabl . krapsack, (urea iva], capacity 5 n)4 ink dp(ni][capacty +1]; ecopacityt d memset (op, haveiler)s Tnitiel zation of table with “a”. wt dp[wo2} [1002] Jet's oie dhe conshaints memset (dp, -I, sizeof (oH); capacty Kodo iv knapsack (iuk wtlJ, it voll}, it copacity, int mdf iF(n==0 IN enpacity ==0) rehnn 0; Vi Cdp(n] [opacity] t= -1) yerun dp (] Ceapacty] 7 if C wt{n-1] <= caese pL feapacity n-1) 5 Knapsack (wt, vol» capacity, 0 ~ alse if (wt[h-!] > capacity] Beta leopa J) = knapsack(wt val Copactty, n- -); Scanned with CamScanner daGepaeh) = Yall ra + newer (le |, capacity soa uy i f 7S ey 2 Botlom- up Approd) 6 prech T] To this only table is there { 1 gag.) Why bsttor- up approach is best? BS oer iap ‘approdzh, Is Bests Cae it auoid the enor of stackoverfiow enor. 3 Reaursive —>Rc colb 3 Memoization —> Rc + FEET mo aha) a Botton - up — Step t+ Gnitialization See2 Reaursive | convert this] texative relation ' a4 ntl a past a ee TOT Scanned with ComScanner 4¢ wif} = [1] 3] 4+ val} = (7 [+] 5 7] wed CTT =6 ¥ INITIALIZATION Cti1t i r i i ? ( 4 | Max Profit 2 » U1 wt=[1,3,9] vol = [1,45] = Wee o Wh intaltgaey_s importa 2 Whi Gnverting the ‘vecursive calu to the elation ... \S Then the base condition of vecursive calls COUT 2 i 2. i iterative AT. Vr (i | changes into ¥ a Thitialization in the iterative Sol. 117 Scanned with ComScanner bPPDDDDDAARABAAAAaAMAOi AMAA Renal Tterative if(n=s0 Il We=0) foy (iso, Tent 5 itt) Ff setuin 0; for(j-0 5 Iewtt 3 J40F iF(i20 II j==0)f apliICj]= o% $ ? if (ut (n-'] <= Wf Flat [r- Tee an raf vo] + Kopel val, bf SPETDM] = meee] + pO DLW - wll " aie val, W, 0-1) # a’, pln - () else if ( wt{n-JJ.>w) vyeturn Knapsack (tats val We m=); aise FCut{n-]> w) ph ]h] = 4ph-IL]; Scanned with ComScanner E VULULUUUUUUIUTOELY VULLLUULOCCOTES Code *- int frapSack (ind wtEJ, int val] ,int 9, int w)i Vector Gvector > Ap (At! > fer(Int iz0; i subset= {3,8} 3 a4e 3 + _§ 67,8 Sto wu FIF\F EFFI IF OIF EE we w ze Tf size of array 7=0 stl) we can creat wlth subse qm zo [Oph sabe Bu if the avroy of size ==0 and sum >o — Then we cant creat Sub. = G Iuskalice with | vel Scanned with ComScanner PEELED ELLELECEELEEOCELELCECECCODOLEDS for (int ico § inti s itt) f for(int j=0 jcsumt ; 4+) § if (i==0) 5 roy = false; if (j=) § OP OIG = trues wating Suvs ap (radlQued] 3 dp ne Cumai) wtC] — ar] \Ww— sum Scanned with ComScanner ogpsnck iF Ct G-) <2 j)f PUIG masflaii-+ apt A G5-ut0-a 4plIQl= éplej-an fi] ap C-JQJ else 4eCIGI= 4P6-Jy Subset = Sum if (arr (t-i] <=5)f \l pA] GI> else apCOG]= dp G-IGI: alae eS 5) Scanned with ComScanner = pm » Equal Sum_fastition Problem fora Te Ca Given an array , we have *o find too diff: ‘th Subset Such at sum of their elements Shoutd be Equad ea © problem statemest © Sinilay with subset sum @ Oda] Even significance @ Gds variation | a= [1.5.05] = = aa we > r > —— > > > aad Fe > The basic condition is = if the Sum of the away eluments ig even —> “Then only we can divide the array ) ; ofp 2 Tras es fig * § 19083 a sts =! bn | a ae | y _ aw re D Else we can't do the partition D Jd ~ int. sum =o; > for(int =o 4 '< size 3 i++) f ~~: sum +2 an(iJ; = | if (surgg| #0) — retum false: ail ——— S > are [1, 9." 65] —> sum = 22 > Now for qual postition —> 2% " " so we howe to find the subset whose sun ig We J into subsel sum u TER So Thi blem now 4s conve fee 02 problem VU Scanned with ComScanner if (sum 72 =o) Jeturn subset Sum (an, sum/2) + for(int isos ign 144) § Sum+= an iJ; 5 if (sum/ 2 }=0) retum fove if(sumya seo) retum subSetSum (amr, Sums); Scanned with ComScanner Rae 22 LLIILADDD DD © Oromo. i> CEOUEEUTUOUTCOETY Gf a’ PULULELELOCOCOEL Count of Subse with a event Gane : an (J = [2, 3,5, 6,8, 10] Sum = jo ay lz We hove t count the number of Subsel with the 2l3a[s]é] ef given Sum. Sum=lo0 {2,83 §2,3,5t } qeere {io} an} = {2,3,516, 8, 10} Sum = 10 U(nti][sum +1] IH) > Su 6 ieee & NS § F 81°95 Je 071 Fo Ve Vo \Fo Vo \FolFo fo \Po Vo wm \ 217) \ 3/4 eet s|w7 w 6 Ty fF <0 Subsets . fro i3¢ sos, ST 5 PO subse Scanned with ComScanner r ————=£=_<=_—_———)\ or if (awGi-i] <= 5) 109 = t0-o09 Wt A Uj-onl-) “Excud Tcl else Exclucle t0JG1 = t0-0G] sqaQ but Subset Sum coeds —y yelum type was bool SF aay of the parameter ig true thew IF Was giving inde buk Her, the return ‘type is eat uni chee Memes te cout the fof Subsets of CONG) = CFB I tO G- an] T i Fo ow > /to=) F WoT ——> 04) FJ R oT ——> Ity= 2 « F an —> oto=o ‘Go Fn # of Subsets with given sum we hae to add both param eter SOGo 1ew 1G) - 0-WGI + 26-0G- onG-] ce Scanned with ComScanner p= * Sin Ss ree a ® an{j= [fe fu ds J output = 1 aT S % Si < Sz S\+S2_2 Seu —> Equol San portion ie.| S)-S2=0 But in thio question > Fee difveremee: (absslute) of, _ hould be minimum {| dn the above example, ; the ules having the valninuens olifference fl.6. 53 {ny +645 {2 W (2 -") — @ Auer PUUTUTECEUCCTEECEUDELEULITELE LOL Scanned with ComScanner fe Equal Saw Petition | . [Te problem is similar wll [ite] qs Now we have to find the rouge of po suw vf) postitiono i Sum | Sum WHAT COULD BE THE RANGE P €t s oi vat Seo 18 OY cota Ns or Subset having att the elum euky 4a Sees $116 Sit a) Phe the range jis (0, 23] of Cun HNKNREEAATTETGIIES din 12 8 4 5S7 2 og ee ea ea Oo *e Scanned with ComScanner VT ee Ut a ‘t | TTT (Cause You caunst make a subset _ op He S/S m gsens Sores whose Suv do (6 Se Now dind out How ay eubies on the nunber Le Salisfies” the ceuclition om Meam can we make S O from de ny Kee 6 [s2 = §0,1,2, 3, 7, 2,9, 103 Tx 24 © This amay consists both S; and Sx. if Sset thew ®(Saw-1) 7 is abo preent > ie. 29 if Sp22 —> (Zarw-2) — is aloo preent > S23 > (Zan -3) a @)is ato prset so cum See 5 we 2 ca So Scanned with ComScanner Fn . SO basic we have fo gind He oly one pemitions another palin will stata dived . (Si- 82) painimize > (2 - SI) 5 wimninice (CRouge-S.) - 8) (Range - 2S)]——-sMinimize . Range is voting but {Zi} s &) (Sir Sed 1 | rae wiwiiro > Sa 3S ~ esp ve) von Zaw S)— Smaller S29 Greeter ada TP TAT I I 3333875. Scanned with ComScanner Jock > similar! fia 4 will Ps . he J Whek does His block is will_tell 2 Size of Gray =| > $13 Lsums7 So This problem cil Solved by the coce St will chk hetrer we a7e geting the cur j | ao 7' or net Bee ca nae hehe ek ee Scanned with ComScanner —————————————Or— Subset Sunline aw[], int Rouge ) f 2 2 3 ¢ s ¢ 7 & J ° [ T Ty 7 (l2\7 sum=y 3 Neches T]a17] sums: > ~ T]217] sug T]2|7] sacle We any ced Hu loot mid oh The cp tM Scanned with CamScanner AIA TIS — : , , ' TI odd She oii “aed 6H half 87 = . Ccame x wout to Boge =10 > FO Se stove Smaller EET lef cs int mini = INT-MAX; for(int iso 3 icvec.sizer) j i++) S mini = min(mioi, Range -(2* vecliD))s 4 veluin mini; Scanned with ComScanner aan er vi a - CTE] OT ge otP E ra Se Ee OTs] CREJ 24-371 fr [s-sa=dp occured 2tmes So we cau take hee oy * Ls cabled dif 00 -dlyy* sum(5,) - Sum (Z,) = diff ar €O® sum(s,)+ S (so) = Sum ‘an ) 2sum(s.) = tiff + Sum(ar) _) S 3 Qsum(s) = ifs + sum(ar) Qe mls Scanned with ComScanner ¢' LECT VTEC OTe T CUOULUUUCTTTTTTTTT Whew suv of subretd is + then only we haue tat the given li . he. Si= 5 = df count 2 os we hove ty Comt So we have reduced ‘this Cassel # cout of Subsets to J GutGout of with given aiff - QGitsetbiun ‘nt sum = dy + Sum(ar) a cretum cous of Subset Sum (ore, sum) jut coutepSiubset Cuan (intl ] arr, tut Gu) [3uibi alization Afrewening 1f (an Gi] <=) GIGd = ti-agI+tG-ILj- aw (i-OJ> ee tI] = t0-OG) return Cn] ou] 5 Scanned with ComScanner += Allowed dike we can toke ay of the sign to any chavo ee 1 os¥-2 43 |— gum=! +H +1 +20 -3 | — sume! 3 F Ww = +3 | —> sum=!| Thin jo Some ay Hoa touuk of Subset sum alifh el: Lp ayy TTT TITIAN ete tet tet teteenee, Scanned with ComScanner TH » Tt rE >» PP SS wa E © Related problems re © Red cutting @ Gin change - I @ Goin change -11 ® Maximum Ribbon ct > $n unbounded Frapsack » multiple occurvences of item is allowed. ! 2 Jn oft knapsack, If we include | Exclude the item, then ik 4 is Considered ao processed item. Means, we Can't considan” | in {uitia ‘duration . | 3 | eae Knapsack , We Can consider a single item 5 mutipe | t mn , 3 &. "Jet's Suppsse 1 like Ice-cream, then I can take Ice-cream multiple times and If 1 don't wand burger, then Ill not consider it leveu Jf it has been Offered fo me multiple time, -UDVELELELELELEGEGOGUGY ruu Scanned with ComScanner In o]) knapsack pans —> processed” (Tr em Exeide processed iS In unbounded eon “a Tnelude —>IN PROCESS oe" Exduds— processed G@de Variation ee Nometiga's OfL lenapsack cock > ee eae ees O1o/0 lect Col T | if(wG-d cy) 1GIG) = mox(votG-4 + rG-]G- wtCi-], G-2G)): Is lo ° lo ebe t0IG) = t0-IG7 dn thio, if we Considiy the ekunent then we ade Th. Value of, that eumeut and we move finard i.e ,(n-1) but in unbounded Kuapsack 5 we can take the eluent mattiple times So we cont have to on, veriofie Frit (i-i] <=i) tOIG) = mo (valG-THOIG-ot0-T] , t RIE): else (IG) Seg t0-ac9 TT Scanned with ComScanner D Th? i I VV0T0E pUUv L Cte 1 i, é 1F) Lb L U L VLEGCCCCUTY * [ieee rae it infinite You ave given a vod of length’ N’ 5 you can cut inthe no. of times . price away is given, Such that -yeu-ean we ot Cut the od with length ‘i’ then you can take the pri thot plece em price (iJ. xy =~ dength(] = [iT ay a]els | ¢ [7 pie CJ = ['] 5] 3]9 |] rp tt] tt] 20 N= 8 aw Simulation : wwe ee te WO de ——~ om 7m e ie pees’ on a itz eg profit cmos oS oe 2m am ai Amn St+5+5+5 dengtle 4 md Sometimes the Leng th ory 40 nol avers ua the uate es we have to Al the “Length anray oy puokiug + fo elements jn the length anay es Ni: W: pre(]= TM tO =e i a duo | VOC] = a) knapsack Ws 3 Ww pree(J—> voll] dengihEJ a wil) Here , we cam cut md de in Same sen Like 33,2 Ds i f unbounded | —Eagsack. ‘Variation Scanned with ComScanner ZZ NI ILI IOI ILD DP Perr werenene-anal Code if(engph (iA <= DE apCIEjI = i G+ pCi T- toyhfD) ; ap i-IGI else f apliG]= pCi -TEfI: J PE VEDLEEELELELELEELECECEECCEDOLOOY Scanned with ComScanner * [Gin Gage 7 coinC] = t 2] 3 Sum = 6 Tnfinite Sippy of coins 243=5 2424155 5 we (Fl+3=2 5 mt (414142 <5 (4)40 +141 eS Now we fave to count the ro. of wow au whiek, we can obtain the given sum but to Knapsoek , two arrays (at § vot) were oo Hor whenever an Garay do jon Thin considy 6 ao wt one MATCHING coins] ——> ut Cl] Sum ——3 W —s Thio is unbounded fovapsack cawe crepetation is aUiowed. Scanned with ComScanner Hurt. ee IPT IDI OS ON ee weeeeyeaa VOLVO LULELCCUCCOCECOGOLLLUUY YY ™ = { vi epanits nis Subset ve eS The questions rrlated fo Subsetfum job a1 1s sao FT $1,253 << > Fale Ga 4 CanGi-J <=) +639 = t('-JGI Il tG-OGj- wD); else tGJGJ= tG-GI; Gout of Subset Summ farli-] 5 = ae ad #oingz3 e439 HS ~™! . Hains 2 3 <— 2 FP He & ap[oins sized) +1 ][sum +] 4e(4]( > Sum oo 2) 8 oe ‘ |»(INT. MAX -1) ' o t Twist we 1S Ha alo SS wu Coin] + $ f So We Tan't make ps Sum=1 thio situation Means coins away is emphy So we require infil were 4 come whic fume up to @ sum vel but we can't take imap in that So tore [INT.MA Cn +12 (e's fale atter they a Scanned with ComScanner DEGULUEUUUUEE EELS it L u L L L L L CLLEECCECE if ow= [3 Ts To] Faw |sTr] but Length =! Sum= 4 al Bi man: no. ef Coins clunomination 3) 4 23084 in Such that We get Sum = 4 yun 2 ; mee (Nor PossrBLE) ° (Int-Mar-1) Scanned with ComScanner #(SAanG}y-— pet t f (J Xaw[i J20) put INT-MAX-! for (iné joi + jesumt! + j++) #G 7% ane] ==°) oT a for 401GI> 3/eG] ee Means else iJ G]= INT_max -! ow the-real tae =D and C= for (int i=2 5 Tends 3 itty Aon fio (int j21 3 jesumat simop gt ow ear if (Snb-1] <=j)f te ot e0IG) =e IL j- eins(j J] t6-IG1) bse i tHIGI= t0-9G13 J Ss new ord Scanned with ComScanner VAs dd dada Toes. ¢ WUT TTT ATTY t CUCU TATA for(int i=2 5 tent i [449 folie jot 3 5 jssum4i ¢ ytt)§ if (ainsfi-d) c=j) aplidLjl- (se coins (i-J] @) de Ci-JLI.. be © afiteling i 8 spCIG] = de0-IGJ For this . we have taken INT.MAX -1 Why INTMAX- 4? Coupe 1 is get added thn INT.MAX Ate = INT_MAX @ But whot if we take “ INT_MAX shstecd oh [INT Max -1 Tf INTMAX and yf we add +1 Cant max +> ly aud Hs value ge cant be abe to store M integer So thals w we hone fo take INZ MAM) Scanned with ComScanner est Common a Subsequence + e pe ems O Longest Common Substring — ®© Print Longest Common Subse quence © Shortest Common sSupersequence @ Print shortest common supersequenee © minimum number of cleletions and insertiom a—>b Longest vepeating subsequence Length of longest Subsequenee ef ‘a’ which is ayenng Subsequen ce Pattern Matching Count how many times (@) appear as Subsequence in@B) J Longest palindromic Subsequence . Longest patindromic Substring Coumt of palindromic substring Mintmum nv, ef deletions in a string to make it a éndrome. Minimum no. ¢ Insertions ina string to make ita patin drome. @ ©@2OO Ge @® ee Scanned with ComScanner = SRS int Les (string x, Shing Y> int m ,int m)§ if (n= Th & LCS, Lungths of shings changing MW 4% —I| ARE CHANGING plat (mel \S luitiakze with £1’ meee ery Answer J SQ & RO —> Here, we will chak whether thio ion ts pepe eallél or sy __How To CHECK ae eee check whether the whether the valu is present in the table or not. Scanned with ComScanner DOULUEUUVEUCOE Ee G66! VELLELELLECOCOC CEE [Ga] 2 9!) ns Hi globin declaration of the table Static int dp [ooi)fooi] ; int Les (string x, String y, int no, int m) § if Cape Ony $= 1) 5 } Yeturn dp{n] im] 3 (xO == ym) 5 dp[n][m]= 1+ les(xs 45 n-l5m-1); 3 else f dpla][m] = max (Se /n,m-1) ‘ / Les(a,y,n-+ym) /” 4 vefurn p(n] [m] ; Scanned with ComScanner CE a base condition 7 in yeuursion Initialization in bottom -wp if(m==0 In==0) — zero utialre EL Tp ee x:abef — m=4q yr abed of 9 neg dp(s [7] — > dpfmtil[n +i] — > * Cylengino) m Catength®) I Tnitializat on dp(m+i](n +) 5 for(int i=0 5 iem+! int joo 5 J¢n4 sje) if (i==0)) J==0) clp(iJGI = 0: 24+) Scanned with CamScanner Ly fl fl edit a alga as LUGULUUEV UTE EE EEE |e d \ CUTE L LCE for(int it 5 icmers itt) § f° for(int j=! d yontl + ytay £ if (x@-J== 4G-D5 ép[iIG] = 1+ apLi-dG~) alses GIGI = mox apCIG-.\ . — (ee): t 3 teturn defn ][n]s Scanned with ComScanner * Tenge omen slg) “Two shings ave given: Si = “abede” Sa = “abfce” 4n Sub sequence Shit Subsequence Can be gourd by skipping ‘Some chatacters betweeh the Si has x Si “abcde Perabce — abce Sas = But in Sub string + & answer should be continuo cu. si= “[ablee——> dle av the Sat fablseey Ob Substrings Longest Common _ ah, Substring W Thitialization poo = for(int i=o 5 Tema s+ for(int j205 jane sjt4) if(izs0 1y=-0) “pCIGI=0 I Main code for(int i=ts icmt 5 i++) ¢ for(int jet 5 Fenty 2 jth § iF Cs\0R-J == saG-D)§ ae ali t1 lke ‘ be OIC) =0; 3 3 TeeGate pap PAA Scanned with CamScanner ‘eel shing 617 “acbef"* Siring S2- ~abcdaf"? Longest Common Subsequente = “abet ® “Task ig to print the Les qf fee stings. How exactly UcS worgs ? sc, = “acbcf" om? 5 S2 = “abcdaf”—9n. ¢ pln} [nei] Pres es +5) o 1 32 3 4.5 abcdlot fe of olol elo Giike His sting is at foPAT| fit tio there GE, afoli li f2l2| 2ial b3f/e jf 1} we}e]-2 | 2 Moan, c+fol:fafalal 3 [3 “ fsfols [2 [3[3l3 4 ™ iso, jo SL == SAG] 9 azza (ove H8D AB Fre Troma 50 aplIgi= dpli- ao At iz0/jot —9 SLi] f= GJ So dpGi GI = mae (oreo) FEI OUUYLUODUEDEEECEECEECEEUYLOLLOEDS a Scanned with ComScanner Herd Rae Sam " £55 “we will a0 ” Now a $c oli fcba”’ are not equal jagonolly go find max (3,2) and move to thet Reverse c) cell, 3 is max % . Sd move left aber Thin pres we have to follow Tis wo ey Equol oe if Not Equal (i,j) Vedado sgooas Scanned with ComScanner EEE EO OOUELEODOEELBEETE Y é CULCE CC eee @ Prepare a table for LCS @® Now we have to start from while Ciro $F jroj if (silt == ssGj-DE ans += S,[i-Ji the (ast celt ge J j else f if (opi G-] > ee 6- TGV jerk J else ap j crevense(ans.beginC) yans.end()) ; eturn ans; Scanned with ComScanner EES ” Bier rer Spear) Sting qi “geek” String b* ~ eke * merge Merge them in such o Woy that [Seelee | both * doar oe “This is the Shovtest Leng He tas *pgqTAs" bs “@xTyaye" FR eet AGGmING GXTx AYR FAGatABGyTXAYS |-> Supersequence iene the Shortest: Spersequence(tenat) a: "AGGTaAg" b: “GxTxAYa” peaXT Ay AGGTAB 1s present GET XAYR > present ft This is the shortest Supersequence Length =g Scanned with ComScanner POR MNNNNLLNIDIIIINI NY We were eewwwee A : art. there as “AGB TAB = ae dh bi G@ Tx aye falren AGGXTXAYB Longest Common Subsequence @) What Would be the worst cae of raking Supersequence + Q: AGGTAB bs GxTxAYB goody Ne Raging # axrxave Us= “QTAB” y lcs =GTAB" worst AGGTABG xTxAYS os me} length of Shore Supers equence =m+n | m+n - dength of\ : ucs i Shortest length of Superced uence . Scanned with ComScanner CPULCCCCCOCCCTUTCCTUTT TTT ut UCs(shring a. shih by int mm, fot int dp [m+] (nag, for(int iso, j¢ mats itt) J for (int jro i Jontry p44) 5 if (izz0) apg] £0; if (j-=0) pli] =o: j for(int izt i jcmey 3 ite) ¢ for(int Jel janes iH S if Catt] == 6-0) OPO] = + dpli-G-0 ; else f dol] (JJ = mox (401-4. apl-G7); 5 Dy pif a i i a hihi oo lel 5 f return dp (mJ C9], } yat maind)$ string a,b; ciny? a>?b; a.lengthc) + b-lenghC) - Les (@,b,alengiht), cou << ateng J bead) j Scanned with ComScanner Tnput :- a: “heap” Output: eaten | bs" pea Deletion. 2 a convert. heap pea 5 fate thin y we should aft Les or not ? Two Strings ore given $ optimal anawer is required Then it is a variation of Les prblem . pea —— pea auf pea Remove ¢ P ee . Gnsertin) elt) amp “0a” remain untouched gemein untouched Co (a) , WHAT IS "@a" 2 q convert, | Le? GEES We will do mak juasp dive, \edy ———— pes bl Gotan ay + 2 deletion A insertion in*ea’ to WP fom ta to C20) Convert to'b) Po tonvert to Ks ss y ke Th WH TUTTO OCT 1 Scanned with ComScanner 2 dwevaen oh bevivesr motivecni > sottstel “o .oA mwantatl |e s . * | . i ani Ed Codes lcs ( string a, String b. int _m, int n)5 dplm+iJ [n+]; MI Tratiatszation fi oS HM wrote code (int iets iemsis itt) § Forint j=1 sen 5 j44)f F(aCi-J == by-7J i] f= VG ones ODF 4p FIG = 14 apG-0g “PCIG] = mae Cap (1-GD, a CITA); LybWguudaIIasodaddad, f } return apCm] (0), 3 man () f Mmput ait b Shrings Gut «.“ PetetaT Min. deleHom " .lengthc)- Les eb,on a) cout < “Min. Insertion “<< b-lengiho, -Us(a, om bi mn)

You might also like